Turán densities of complete hypergraphs

DefinitionEdges of the complete uniform hypergraph#✓fully proved

For natural numbers \(k\) and \(m\), the edge family of the complete \(k\)-uniform hypergraph on the vertex set \(\{0, 1, \dots, m-1\}\) is the family of all \(k\)-element subsets of \(\{0, 1, \dots, m-1\}\).

def completeHypergraphEdges (k m : ℕ) : Finset (Finset (Fin m)) :=
  Finset.univ.powersetCard k

Sources

• [AIM-COMBINATORICS-0149], aim-combinatorics-notes.json notes[148], Source item 11.3, Section Complete hypergraphs, Workshop Hypergraph Turan problem, Source URL http://aimpl.org/hypergraphturan/1/.

Used by 1

Used byTurán number of the complete \(k\)-graph on \(k+1\) vertices

DefinitionTurán number of the complete \(k\)-graph on \(k+1\) vertices#✓fully proved

For natural numbers \(k\) and \(n\), let \(K_{k+1}^{(k)}\) be the complete \(k\)-uniform hypergraph on the vertex set \(\{0, 1, \dots, k\}\), whose edges are all \(k\)-element subsets of that set. The Turán number \(\mathrm{ex}(n, K_{k+1}^{(k)})\) is the largest size of a family \(E\) of \(k\)-element subsets of \(\{0, 1, \dots, n-1\}\) that contains no copy of \(K_{k+1}^{(k)}\), that is, for which there is no injective map \(f \colon \{0, 1, \dots, k\} \to \{0, 1, \dots, n-1\}\) such that the image under \(f\) of every edge of \(K_{k+1}^{(k)}\) belongs to \(E\).

noncomputable def turanNumber (k n : ℕ) : ℕ :=
  let forb : Finset (Finset (Fin (k + 1))) := completeHypergraphEdges k (k + 1)
  let all : Finset (Finset (Finset (Fin n))) :=
    ((Finset.univ : Finset (Fin n)).powersetCard k).powerset
  let free := all.filter (fun E => ¬ ∃ f : Fin (k + 1) ↪ Fin n, ∀ e ∈ forb, Finset.map f e ∈ E)
  free.sup (fun E => E.card)

Sources

• [AIM-COMBINATORICS-0149], aim-combinatorics-notes.json notes[148], Source item 11.3, Section Complete hypergraphs, Workshop Hypergraph Turan problem, Source URL http://aimpl.org/hypergraphturan/1/.

Uses 1 · Used by 1

Statement usesEdges of the complete uniform hypergraph

Used byTurán density ratio

DefinitionTurán density ratio#✓fully proved

For natural numbers \(k\) and \(n\), the Turán density ratio is the real number \(\mathrm{ex}(n, K_{k+1}^{(k)}) / \binom{n}{k}\), where \(\mathrm{ex}(n, K_{k+1}^{(k)})\) is the Turán number of the complete \(k\)-uniform hypergraph \(K_{k+1}^{(k)}\) on \(k+1\) vertices, the largest number of \(k\)-element subsets of an \(n\)-element set containing no copy of \(K_{k+1}^{(k)}\). The ratio is defined to be \(0\) when \(\binom{n}{k} = 0\), that is, when \(n < k\).

noncomputable def turanDensityRatio (k n : ℕ) : ℝ :=
  if n.choose k = 0 then 0 else (turanNumber k n : ℝ) / (n.choose k : ℝ)

Sources

• [AIM-COMBINATORICS-0149], aim-combinatorics-notes.json notes[148], Source item 11.3, Section Complete hypergraphs, Workshop Hypergraph Turan problem, Source URL http://aimpl.org/hypergraphturan/1/.

Uses 1 · Used by 1

Statement usesTurán number of the complete \(k\)-graph on \(k+1\) vertices

Used byTurán density of the complete \(k\)-graph on \(k+1\) vertices

DefinitionTurán density of the complete \(k\)-graph on \(k+1\) vertices#✓fully proved

For a natural number \(k\), the Turán density \(\pi(K_{k+1}^{(k)})\) of the complete \(k\)-uniform hypergraph \(K_{k+1}^{(k)}\) on \(k+1\) vertices is the limit superior, as \(n \to \infty\), of the Turán density ratios \(\mathrm{ex}(n, K_{k+1}^{(k)}) / \binom{n}{k}\), where \(\mathrm{ex}(n, K_{k+1}^{(k)})\) is the Turán number of \(K_{k+1}^{(k)}\) and the ratio is taken to be \(0\) when \(\binom{n}{k} = 0\).

noncomputable def turanDensityComplete (k : ℕ) : ℝ :=
  Filter.limsup (fun n : ℕ => turanDensityRatio k n) Filter.atTop

Sources

• [AIM-COMBINATORICS-0149], aim-combinatorics-notes.json notes[148], Source item 11.3, Section Complete hypergraphs, Workshop Hypergraph Turan problem, Source URL http://aimpl.org/hypergraphturan/1/.

Uses 1 · Used by 1

Statement usesTurán density ratio

Used byDe Caen's conjecture on Turán densities of complete hypergraphs

DefinitionDe Caen's conjecture on Turán densities of complete hypergraphs#✓fully proved

For a natural number \(k\), let \(\pi(K_{k+1}^{(k)})\) be the Turán density of the complete \(k\)-uniform hypergraph on \(k+1\) vertices. De Caen's conjecture asserts that \(k \, (1 - \pi(K_{k+1}^{(k)})) \to \infty\) as \(k \to \infty\).

noncomputable def conjecture : Prop :=
  Filter.Tendsto (fun k : ℕ => (k : ℝ) * (1 - turanDensityComplete k)) Filter.atTop Filter.atTop

Sources

• [AIM-COMBINATORICS-0149], aim-combinatorics-notes.json notes[148], Source item 11.3, Section Complete hypergraphs, Workshop Hypergraph Turan problem, Source URL http://aimpl.org/hypergraphturan/1/.

Uses 1 · Used by 1

Statement usesTurán density of the complete \(k\)-graph on \(k+1\) vertices

Used byDe Caen's conjecture is false

TheoremDe Caen's conjecture is false#●ready to prove

It is not the case that \(k \, (1 - \pi(K_{k+1}^{(k)}))\) tends to \(\infty\) as \(k \to \infty\), where \(\pi(K_{k+1}^{(k)})\) is the Turán density of the complete \(k\)-uniform hypergraph \(K_{k+1}^{(k)}\) on \(k+1\) vertices.

Pikhurko (Adv. Math. 464 (2025) 110148, Theorem 1.1) proves \(T(n, k+1, k) \le \frac{6.239}{k+1} \binom{n}{k}\) for all \(n > k \ge 1\), where \(T(n, k+1, k)\) is the least number of \(k\)-element subsets of an \(n\)-element set such that every \((k+1)\)-element subset contains one of them; hence \(k \, (1 - \pi(K_{k+1}^{(k)})) \le 6.239\) for every \(k \ge 1\), and the paper states that this disproves de Caen's conjecture.

public theorem_wanted conjecture_refuted : ¬ conjecture

Sources

• O. Pikhurko, Constructions of Turán systems that are tight up to a multiplicative constant, Advances in Mathematics 464 (2025), 110148, https://pikhurko.github.io/E/Pikhurko25am.pdf.

Uses 1

Statement usesDe Caen's conjecture on Turán densities of complete hypergraphs

5 fully proved1 ready to prove

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.