A problem of Laczkovich: How dense are set systems with no large independent sets?

详细信息    查看全文

• 作者：Pé ; ter Komjá ; th¹ ; ^{kope@cs.elte.hu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：03E05 ; 03E35 ; 03E50 ; 05C65
• 刊名：Annals of Pure and Applied Logic
• 出版年：2016
• 出版时间：October 2016
• 年：2016
• 卷：167
• 期：10
• 页码：879-896
• 全文大小：445 K

文摘

We investigate the function L_H(n)=max⁡{|H∩P(A)|:|A|=n}$L_{\mathcal{H}}(n)=\max \{|\mathcal{H}\cap \mathcal{P}(A)|:|A|=n\}$ where H$\mathcal{H}$ is a set of finite subsets of λ such that every λ-sized subset of λ   has arbitrarily large subsets form H$\mathcal{H}$. For κ=ℵ₁$\kappa ={\mathrm{\aleph }}_1$, lim⁡L_H(n)/n→∞$\lim L_{\mathcal{H}}(n)/n\to \infty$ and 16e79411c55355ca7" title="Click to view the MathML source">L_H(n)=O(n²)$L_{\mathcal{H}}(n)=\mathrm{O}(n^2)$, and in different models of set theory, either bound can be sharp. If λ>ℵ₁$\lambda >{\mathrm{\aleph }}_1$, L_H(n)>cn²$L_{\mathcal{H}}(n)>c{n}^2$ for some c>0$c>0$ and n sufficiently large. If λ   is strong limit singular, then L_H$L_{\mathcal{H}}$ is superpolynomial. If κ<λ$\kappa <\lambda$ are uncountable cardinals, we call a family H$\mathcal{H}$κ-dense (strongly κ-dense) in λ if every κ-sized subset of λ   contains a set (arbitrarily large sets) in H$\mathcal{H}$. We show under GCH that if H$\mathcal{H}$ is κ⁺${\kappa }^{+}$-dense in κ^+r${\kappa }^{+r}$ (r   finite), then L_H(n)/n^r→∞$L_{\mathcal{H}}(n)/n^r\to \infty$ (κ=ω$\kappa =\omega$) and L_H(n)>cn^r+1$L_{\mathcal{H}}(n)>c{n}^{r+1}$ (16e42fefdfa0" title="Click to view the MathML source">κ>ω$\kappa >\omega$). We also give bounds for L_H(n)$L_{\mathcal{H}}(n)$ when H$\mathcal{H}$ has large chromatic or coloring number.