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 statement4 of 4

The construction of Ma and Tang [MaTa25] of a graph with $n$ vertices and $>n^2/4$ edges in which every triangle has at most $(2-(5/2)^{1/2}+o(1))n$ vertices adjacent to at least two of its vertices shows that, for the threshold $h(n)$ of erdos_1034.variants.lower_bound, $h(n) \leq (2-(5/2)^{1/2}+o(1))n.$

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

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

SolvedStatement only, no proof

Sources

Search problems.science