The asymptotic behavior of the covering number of a graph on two layers of the Boolean lattice

József Balogh, William Linz

Published 2019-10-24Version 1

Let $n > k > \ell \ge 1$ be positive integers, and define a bipartite graph $G_{k, \ell}=(V, E)$ by $V(G_{k, \ell})=(\binom{[n]}{k}, \binom{[n]}{\ell})$ and $(A, B) \in E(G_{k, \ell})$ if and only if $A \in \binom{[n]}{\ell}$, $B\in \binom{[n]}{k}$, and $A\subset B$. We confirm a conjecture of Badakhshian, Katona and Tuza for the two-sided covering number $\gamma(G_{k, 2})$, for fixed $k$ and $n\rightarrow\infty$. Additionally, we prove a general lower bound for $\gamma(G_{k, \ell})$, with $k$ and $\ell$ fixed and $n\rightarrow \infty$. Our proof uses the graph removal lemma and a Frankl-R\"odl nibble type theorem of Pippenger.