A problem of Laczkovich: how dense are set systems with no large independent sets? (Q2630826): Difference between revisions

A system \({\mathcal H} \subseteq [\lambda]^{<\omega}\) is \textit{\(\kappa\)-dense} (\textit{\(\kappa\)-strongly dense}) if for every \(\kappa\)-sized \(X \subseteq \lambda\), there is an (arbitrarily large) member of \({\mathcal H}\) which is contained in \(X\). When \(\kappa=\lambda\), it is called \textit{dense} (\textit{strongly dense}). The case \(\kappa=\lambda=\omega_1\) is a question raised by \textit{M. Laczkovich} [Period. Math. Hung. 69, No. 2, 109--119 (2014; Zbl 1349.13043)]. A variation of this function appeared in the paper of \textit{P. Erdős} et al. [in: Infinite and finite sets. To Paul Erdős on his 60th birthday. Vol. I, II, III. Amsterdam - London: North-Holland Publishing Company. 425--513 (1975; Zbl 0324.04005)]. This paper investigate the growing rate of the function \(L_{\mathcal H}(n) = \max \{|{\mathcal H} \cap {\mathcal P}(x)| : x \in [\lambda]^n\}\). \hskip1em The author shows that for every strongly dense system, \(L_{\mathcal H}(n) /n \to \infty\) (Theorem 2) and there is one such that \(L_{\mathcal H}(n) = O(n^2)\) (Theorem 1). The possible growing rates of \(L_{\mathcal H}(n)\) (in particular the case \(L_{\mathcal H}(n)=O(n f(n))\)) for various monotic \(f: \omega \to \omega\) such that \(f(n) \to \infty\) are discussed in Theorems 3--6. In Theorem 9, it is shown that when \(\lambda>\omega_1\), for every nonuniform strongly dense \({\mathcal H}\), \(L_{\mathcal H}(n)>c n^2\), for some constant \(c\). The author also shows that under GCH, if \(1<r<\omega\), \({\mathcal H}\) is \(\kappa\)-dense in \(\kappa^{+r}\), then \(L_{\mathcal H}(n)/n^r \to \infty\) for \(\kappa=\omega\) and \(L_{\mathcal H}(n) / c n^{r+1} \to \infty\) (for some constant \(c\)) for \(\kappa>\omega\). The situations in which \(L_{\mathcal H}(n)=O(n^2 f(n))\) for \(f: \omega \to \omega\) such that \(f(n) \to \infty\) are also discussed. In the last part of the paper, the author considers classes of set systems with large chromatic or coloring number. If \(\mathcal H\) is a system with uncountable coloring number, then \(L_{\mathcal H}(n)/n \to \infty\) (Theorem 17). In particular, if \(\mathcal H\) consists of \(k\)-tuples, then \(L_{\mathcal H}(n)> c_k n^{1+1/k}\) for sufficiently large \(n\) and some constant \(c_k\) (Theorem 19). Theorem 18 and 20 are results complementing the two theorems above.