Erdős problem 1034 · problems.science

Let $G$ be a graph on $n$ vertices with $>n^2/4$ many edges. Must there be a triangle $T$ in $G$ and vertices $y_1,\ldots,y_t$ , where $t>(\frac{1}{2}-o(1))n$ , such that every $y_i$ is joined to at least two vertices of $T$ ?

Sources

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

4 retained statements2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

1034.lean

Retained formal statement2 of 4

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

FormalConjectures/ErdosProblems/1034.leanErdos1034.erdos_1034.variants.k4_free8 linesExact file

1∀ (ε : ℝ),2  0 < ε →3    ∀ᶠ (n : ℕ) in Filter.atTop,4      ∃ G,5        G.CliqueFree 4 ∧6          ↑n ^ 2 / 4 < ↑G.edgeSet.ncard ∧7            ∀ (T : Finset (Fin n)),8              G.IsNClique 3 T → ∀ (Y : Finset (Fin n)), Erdos1034.JoinedToTwo G T Y → ↑Y.card ≤ (2 * √3 - 3 + ε) * ↑n

SolvedStatement only, no proof

Sources

Search problems.science