Skip to content

Erdős problem 1034

Let GG be a graph on nn vertices with >n2/4>n^2/4 many edges. Must there be a triangle TT in GG and vertices y1,…,yty_1,\ldots,y_t, where t>(12−o(1))nt>(\frac{1}{2}-o(1))n, such that every yiy_i is joined to at least two vertices of TT?

Sources

The source's own material, retained exactly.

4 retained statements36c6d0fef71a

Open selected source

FormalConjectures/ErdosProblems/

1034.lean

Retained formal statement2 of 4

Erdős suggested that the answer is different if GG has no K4K_4. In the comments Ma and Tang sketch a proof that the conjecture remains false even if we assume that GG contains no K4K_4, constructing a graph with nn vertices, >n2/4>n^2/4 edges, and no K4K_4, in which every triangle has at most (23−3+o(1))n(2\sqrt{3}-3+o(1))n vertices adjacent to at least two of its vertices (note that 23−3≈0.4642\sqrt{3}-3\approx 0.464).

FormalConjectures/ErdosProblems/1034.leanErdos1034.erdos_1034.variants.k4_free8 linesExact file
∀ (ε : ℝ),  0 < ε →    ∀ᶠ (n : ℕ) in Filter.atTop,      ∃ G,        G.CliqueFree 4 ∧          ↑n ^ 2 / 4 < ↑G.edgeSet.ncard ∧            ∀ (T : Finset (Fin n)),              G.IsNClique 3 T → ∀ (Y : Finset (Fin n)), Erdos1034.JoinedToTwo G T Y → ↑Y.card ≤ (2 * √3 - 3 + ε) * ↑n
SolvedStatement only, no proof