Erdős problem 794 · problems.science

Is it true that every $3$ -uniform hypergraph on $3n$ vertices with at least $n^3+1$ edges must contain either a subgraph on $4$ vertices with $3$ edges or a subgraph on $5$ vertices with $7$ edges?

Sources

Browse retained paths and inspect the exact material available for this Problem.

4 retained statements2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

794.lean

Retained formal statement3 of 4

This problem is then now asking how many edges a $3$ -uniform hypergraph can have before it contains $K_4$ minus an edge, and whether the critical edge density is $2/9$ . In fact there is a construction of Frankl and Füredi [FrFu84] showing it must be at least $2/7$ , which is the conjectured truth (although Turán conjectured before [Er69] that the edge density was $1/4$ , and so likely there is simply a typo in this problem's statement).

FormalConjectures/ErdosProblems/794.leanErdos794.erdos_794.variants.frankl_furedi3 linesExact file

1∀ (ε : ℝ),2  0 < ε →3    ∀ᶠ (n : ℕ) in Filter.atTop, ∃ H, H.IsThreeUniform ∧ ¬H.ContainsSubgraph 4 3 ∧ (2 / 7 - ε) * ↑(n.choose 3) ≤ ↑H.card

SolvedStatement only, no proof

Sources

Search problems.science