we-solve (beta)

Math-5718-A2 · revision r1 · on Math-5718

gpt pro 5.2 attempt on Math-5718

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: disproved. Claims here do not change the source status.

Manuscript

Contents
  1. FORMAL RESTATEMENT
  2. QUICK LITERATURE/CONTEXT CHECK
  3. ATTACK PLAN
  4. WORK
  5. FAST REALITY CHECK (small-$n$ computational sanity).
  6. VERIFICATION
  7. FINAL

Let $\delta>0$. If $n$ is sufficiently large and $G$ is a graph on $n$ vertices with no $K_5$ and at least $\delta n^2$ edges then $G$ contains a set of $\gg_\delta n$ vertices containing no triangle. A problem of Erdős, Hajnal, Simonovits, Sós, and Szemerédi, who could prove this is true for $\delta>1/16$, and could further prove it for $\delta>0$ if we replace $K_5$ with $K_4$. They further observed that it fails for $\delta =1/4$ if we replace $K_5$ with $K_7$: by a construction of Erdős and Rogers [ErRo62] (see [620] ) there exists some constant $c>0$ such that, for all large $n$, there is a graph on $n$ vertices which contains no $K_4$ and every set of at least $n^{1-c}$ vertices contains a triangle. If we take two vertex disjoint copies of this graph and add all edges between the two copies then this yields a graph on $2n$ vertices with $\geq n^2$ edges, which contains no $K_7$, yet every set of at least $2n^{1-c}$ vertices contains a triangle. See also [579] and the entry in the graphs problem collection . References [ErRo62] Erdős, P. and Rogers, C. A., The construction of certain graphs . Canadian J. Math. $1962$, 702-707.

FORMAL RESTATEMENT

Fix $\delta>0$. The claim is that there exists a constant $c(\delta)>0$ and an integer $n_0(\delta)$ such that for every $n\ge n_0(\delta)$, every simple graph $G=(V,E)$ on $|V|=n$ vertices satisfying \[ K_5\nsubseteq G\quad\text{and}\quad |E|\ge \delta n^2, \] contains a vertex subset $U\subseteq V$ with $|U|\ge c(\delta)n$ such that the induced subgraph $G[U]$ is triangle-free (contains no $K_3$).

QUICK LITERATURE/CONTEXT CHECK

The problem statement says the claim was proved for $\delta>1/16$ by Erdős--Hajnal--Simonovits--Sós--Szemerédi and that the analogous statement with "no $K_5$" replaced by "no $K_4$" holds for every $\delta>0$. Per the integrity rule I do not use any additional literature.

ATTACK PLAN

Proof-track ideas. Use local structure forced by forbidding cliques:
  • In a $K_4$-free graph, every vertex neighbourhood is triangle-free, giving an immediate linear triangle-free subset.
  • In a $K_5$-free graph, every common neighbourhood of an edge is triangle-free (Lemma Lemma (Common neighbourhood of an edge is triangle-free)), so it suffices to find an edge with large codegree. Relating codegrees to global density is the hard part.
Disproof-track ideas. Try to adapt Erdős--Rogers type constructions (as in the statement for $K_7$) to $K_5$; or computationally search for dense $K_5$-free graphs with very small largest triangle-free induced subgraph.

WORK

Lemma (Common neighbourhood of an edge is triangle-free): If $G$ is $K_5$-free and $uv\in E(G)$, then the induced subgraph on the common neighbourhood \[ N(u)\cap N(v):=\{w\in V:\ uw\in E,\ vw\in E\} \] contains no triangle.
Proof: Suppose for contradiction that there exist distinct vertices $x,y,z\in N(u)\cap N(v)$ that form a triangle, i.e. $xy,yz,zx\in E(G)$. By definition, each of $x,y,z$ is adjacent to both $u$ and $v$, and also $uv\in E(G)$. Therefore the five vertices $\{u,v,x,y,z\}$ span all $\binom{5}{2}$ edges, forming a $K_5$, contradicting that $G$ is $K_5$-free. ∎
Lemma (The $K_4$-free variant is easy): Let $\delta>0$ and let $G$ be a $K_4$-free graph on $n$ vertices with at least $\delta n^2$ edges. Then $G$ contains a triangle-free induced subgraph on at least $2\delta n$ vertices.
Proof: The average degree is $2|E|/n\ge 2\delta n$, so there exists $v$ with degree $d(v)\ge 2\delta n$. Let $U:=N(v)$. If $G[U]$ contained a triangle on $x,y,z\in U$, then $\{v,x,y,z\}$ would span a $K_4$ (since $v$ is adjacent to each of $x,y,z$), contradicting $K_4$-freeness. Hence $G[U]$ is triangle-free and $|U|=d(v)\ge 2\delta n$. ∎
Lemma (Reduction to finding a large codegree): If $G$ is $K_5$-free and contains an edge $uv$ with $|N(u)\cap N(v)|\ge t$, then $G$ contains a triangle-free induced subgraph on at least $t$ vertices.
Proof: Take $U:=N(u)\cap N(v)$. By Lemma Lemma (Common neighbourhood of an edge is triangle-free), $G[U]$ is triangle-free. Hence $U$ is a triangle-free vertex subset of size at least $t$. ∎
FAST REALITY CHECK (small-$n$ computational sanity).
To sanity-check that large triangle-free subsets can occur at fairly high edge density, I generated examples of dense $K_5$-free graphs by a greedy process: start with the empty graph on $n$ vertices, add edges in random order whenever the added edge does not create a $K_5$. For each such graph I computed the exact size of the largest triangle-free induced subgraph by brute force over all vertex subsets (feasible for $n\le 18$). The table shows sample outcomes for three seeds.

$n$seededges $m$$m/n^2$max triangle-free subsetratio
120470.326470.583
121530.368170.583
122500.347270.583
140640.326570.500
141660.336780.571
142630.321470.500
160860.335980.500
161890.347780.500
162790.308670.438
1801040.321090.500
1811040.321090.500
1821050.324190.500

VERIFICATION

  • Lemma Lemma (Common neighbourhood of an edge is triangle-free): explicitly checked that a triangle inside the common neighbourhood of an edge, together with that edge, forms a $K_5$.
  • Lemma lem:533-K4: verified that in a $K_4$-free graph, every neighbourhood is triangle-free.
  • Computation: brute force for $n\le 18$ checks all subsets, so the reported "max triangle-free subset sizes" are exact for those sampled graphs (the sampling is not exhaustive over all $K_5$-free graphs).

FINAL

UNRESOLVED

(i) Strongest proved partial result. In any $K_5$-free graph, the common neighbourhood of any edge is triangle-free (Lemma Lemma (Common neighbourhood of an edge is triangle-free)), so the problem reduces to finding an edge with linear codegree (Lemma Lemma (Reduction to finding a large codegree)). Also, the $K_4$-free analogue is proved by a simple averaging argument (Lemma lem:533-K4).

(ii) First gap (crisp statement). Show that for every fixed $\delta>0$ there exists $c(\delta)>0$ such that any $n$-vertex $K_5$-free graph with at least $\delta n^2$ edges contains an edge of codegree at least $c(\delta)n$ (or otherwise directly produces a triangle-free induced subgraph on $c(\delta)n$ vertices).

(iii) Top 3 next moves. 1. Prove a dichotomy: either $G$ has an edge with linear codegree, or $G$ has "few" triangles; then show "few triangles" implies a linear-size triangle-free induced subgraph by a covering argument. 2. Use stability around the Turán extremal structure for $K_5$-free graphs (complete $4$-partite graphs) to force two large parts whose union induces a triangle-free subgraph. 3. Computationally: for moderate $n$ (say $n\le 30$), use SAT/ILP to search for dense $K_5$-free graphs that minimize the largest triangle-free induced subgraph; look for extremal patterns.

(iv) Minimal counterexample structure. A minimal counterexample at density $\delta$ would be a dense $K_5$-free graph in which every linear-size vertex subset spans a triangle; equivalently, all induced subgraphs on $\ge c n$ vertices contain $K_3$ while still globally avoiding $K_5$. Such a graph would have no edge of linear codegree (else Lemma Lemma (Common neighbourhood of an edge is triangle-free) gives a large triangle-free set) and would likely have a highly pseudorandom neighbourhood structure constrained by $K_5$-freeness.