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

Erdős and Faudree asked about the threshold $h(n)$ such that every graph with $n$ vertices and $>n^2/4$ edges contained a triangle and $h(n)$ other vertices which are connected to at least two vertices of the triangle. The fact that every graph with $>n^2/4$ edges contains a book of size $n/6$ shows that $(1/6-o(1))n \leq h(n).$

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

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

SolvedStatement only, no proof

Sources

Search problems.science