Forbidding Complete Hypergraphs as Traces

摘要

Let 2 ≤q ≤min{p, t ? 1} be fixed and n → ∞. Suppose that $mathcal{F}$ is a p-uniform hypergraph on n vertices that contains no complete q-uniform hypergraph on t vertices as a trace. We determine the asymptotic maximum size of ${mathcal{F}}$ in many cases. For example, when q = 2 and p∈{t, t + 1}, the maximum is $( frac{n}{t-1})^{t-1} + o(n^{t-1})$ , and when p = t = 3, it is $lfloor frac{(n-1)^2}{4}rfloor$ for all n≥ 3. Our proofs use the Kruskal-Katona theorem, an extension of the sunflower lemma due to Füredi, and recent results on hypergraph Turán numbers.