加载中…
Let K_4 denote the complete 3-uniform hypergraph on 4 vertices. Ajtai, Erd\H{o}s, Koml'os, and Szemer'edi (1981) asked if there is a function \omega(d) tending to infinity such that every 3-uniform, K_4-free hypergraph N vertices and average degree d has independence number at least \omega(d) N/d^{1/2}. We answer this question by constructing a 3-uniform, K_4-free hypergraph with independence number at most 2N/d^{1/2}. We also provide counterexamples to several related conjectures and improve the lower bound of some hypergraph Ramsey numbers.

生成讲解博客的中文版本

生成AI智能校验的中文版本