Description
Consider all $k$-element subsets and $\ell$-element subsets ($k >\ell$) of an $n$ element set as vertices of a bipartite graph. Two vertices are adjacent if the corresponding $\ell$-element set is a subset of the corresponding $k$-element set. Let $G_{k,\ell}$ denote this graph. In an earlier lecture of this seminar we exactly determined the domination number of $G_{k,1}$ and gave lower and upper estimates for $\gamm(G_{k,2})$. Since then we managed to prove that $\gamma(G_{k,2})$ is asymptotically equal to $\frac{k + 3}{ 2(k − 1)(k + 1)}n^2$ for $k \ge 3$. The upper estimate is proved by a theorem of Frankl and Rödl. The proof of the lower bound is based on the Graph Removal Lemma. It is a joint work of Jozsef Balogh, Gyula O.H. Katona, William Linz and Zsolt Tuza.