For a fixed -uniform forbidden hypergraph , its Turán density is the limit of . Averaging over smaller vertex subsets shows these normalized extremal numbers are nonincreasing, so the limit exists. For ordinary graphs, the Erdős-Stone theorem determines it from the chromatic number.
Normalized hypergraph extremal numbers decrease under vertex sampling and converge to Turán density. At a fixed sample size where the extremal density is close to that limit, excess density forces a positive fraction of samples to contain . Counting incidences of copies and samples proves the displayed lower bound. Shrinking also handles the finitely many small orders when the required count is rounded down.
For the complete -uniform hypergraph , with , the bound is . In the complementary covering formulation, every -set containing an edge forces asymptotic edge density at least . It follows from clique-extension incidence inequalities and Cauchy-Schwarz inequality estimates on link degrees.
Articles by others on the same topic
There are currently no matching articles.