we-solve (beta)

Math-691-A2 · revision r1 · on Math-691

gpt pro 5.2 attempt on Math-691

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. Erdős Problem #146 (Erdős--Simonovits conjecture for $r$-degenerate bipartite graphs)
  2. 1) FORMAL RESTATEMENT
  3. 2) QUICK LITERATURE / CONTEXT CHECK
  4. 3) ATTACK PLAN
  5. 4) WORK
  6. Phase 1 sanity checks (tiny cases).
  7. A complete proof for $r=1$.
  8. Beyond $r=1$.
  9. 5) VERIFICATION
  10. 6) FINAL
  11. 7) COMPLETION ESTIMATE

Erdős Problem #146 (Erdős--Simonovits conjecture for $r$-degenerate bipartite graphs)

1) FORMAL RESTATEMENT

For a fixed graph $H$, let $\mathrm{ex}(n,H)$ denote the Turán (extremal) number: the maximum number of edges in an $n$-vertex simple graph containing no copy of $H$ as a (not necessarily induced) subgraph.

A graph $H$ is $r$-degenerate if every (induced) subgraph of $H$ has a vertex of degree at most $r$; equivalently, there is an ordering of $V(H)$ in which each vertex has at most $r$ neighbors later in the order.

Conjecture (Erdős--Simonovits / Erdős). If $H$ is bipartite and $r$-degenerate, then \[ \mathrm{ex}(n,H)=O_H\left(n^{2-1/r}\right). \]

2) QUICK LITERATURE / CONTEXT CHECK

  • A classic special case: if all degrees in one color class of $H$ are at most $r$, then $\mathrm{ex}(n,H)=O(n^{2-1/r})$ (Füredi; also Alon--Krivelevich--Sudakov $2003$ via dependent random choice).
  • For general $r$-degenerate bipartite $H$, Alon--Krivelevich--Sudakov $2003$ proved a weaker universal bound $\mathrm{ex}(n,H)=O\left(n^{2-1/(4r)}\right)$.
  • The conjectured exponent $2-1/r$ is known for large families of $r$-degenerate bipartite graphs, including all $r$-degenerate blow-ups of trees (Grzesik--Janzer--Nagy 2019/2022).
  • For the $2$-degenerate grid graphs $F_t$ (the $t\times t$ planar grid), Bradač--Janzer--Sudakov--Tomon proved $\mathrm{ex}(n,F_t)=\Theta(n^{3/2})$, matching the conjectured exponent for $r=2$.

3) ATTACK PLAN

Proof track.
  1. Settle the easiest case $r=1$ completely (forests), to validate the conjecture at the base level.
  2. Recall the dependent random choice (DRC) template: show that if $G$ has many edges, then $G$ contains a bipartite pair $(U_1,U_2)$ where every $r$-tuple in $U_i$ has many common neighbors in $U_{3-i}$; then embed $H$ using a degeneracy ordering. This yields the known $2-1/(4r)$ exponent.
  3. Identify what extra structure (supersaturation, random walks on auxiliary graphs, tensor power) is needed to upgrade the exponent from $2-1/(4r)$ to $2-1/r$.

Disproof track.

  1. Search for candidate counterexamples among sparse bipartite graphs with bounded degeneracy but unusually large extremal exponent (e.g. graphs with "high complexity" in the sense used in the degenerate Turán literature).
  2. Any disproof would require an explicit bipartite $r$-degenerate $H$ and a construction of $H$-free graphs with $\gg n^{2-1/r+\delta}$ edges.

4) WORK

Phase 1 sanity checks (tiny cases).
  • $r=1$-degenerate graphs are forests. For a fixed tree $T$, it is classical and elementary that $\mathrm{ex}(n,T)=O(n)$.
  • For $r=2$, the conjectured bound is $\mathrm{ex}(n,H)=O(n^{3/2})$ for every $2$-degenerate bipartite $H$. This is consistent with sharp results for $C_4$ and $K_{2,t}$, and with the proven case of grid graphs $F_t$.
A complete proof for $r=1$.
Theorem (Conjecture holds for $r=1$): Let $H$ be a fixed forest on $h\ge 2$ vertices. Then \[ \mathrm{ex}(n,H)\le (h-2)n \qquad\text{for all }n\ge 1. \] In particular, for bipartite $1$-degenerate $H$ one has $\mathrm{ex}(n,H)=O_H(n)=O_H$n^{2-1}$.
Proof: Let $G$ be an $n$-vertex graph with $e(G)>(h-2)n$. We claim $G$ contains $H$.

First, repeatedly delete vertices of degree at most $h-2$ (and all incident edges) until this is no longer possible. If the process deletes all vertices, then the total number of edges removed is at most $(h-2)n$, contradicting $e(G)>(h-2)n$. Hence some nonempty subgraph $G'$ remains with minimum degree \[ \delta(G')\ge h-1. \]

It suffices to show that $G'$ contains every tree on $h$ vertices (since $H$ is a subgraph of some tree on $h$ vertices, obtained by adding edges between components). So let $T$ be any tree on $h$ vertices. We prove by induction on $h$ that every graph with minimum degree at least $h-1$ contains $T$.

Base $h=2$ is trivial. For $h\ge 3$, let $v$ be a leaf of $T$ and $u$ its neighbor. Then $T-v$ is a tree on $h-1$ vertices. Since $\delta(G')\ge h-1\ge (h-1)-1$, by the induction hypothesis $G'$ contains a copy of $T-v$. Let $u'$ be the vertex in this copy corresponding to $u$. This copy uses exactly $h-1$ vertices of $G'$. Because $\deg_{G'}(u')\ge h-1$, the vertex $u'$ has at least one neighbor outside the used $(h-1)$-set. Embed $v$ to such an unused neighbor of $u'$, extending the embedding to a copy of $T$.

Thus $G'$ contains $T$, hence contains $H$, contradicting $H$-freeness. Therefore any $H$-free $n$-vertex graph has at most $(h-2)n$ edges. ∎

Beyond $r=1$.
For $r\ge 2$, the conjectured exponent $2-1/r$ is open in general. Known methods (e.g. dependent random choice) yield weaker exponents such as $2-1/(4r)$, and additional structure assumptions on $H$ (e.g. being a blow-up of a tree) allow proving the conjectured exponent.

5) VERIFICATION

  • Theorem thm:146-r1 exactly matches the conjectured exponent for $r=1$.
  • The degeneracy notion used (every induced subgraph has a vertex of degree $\le r$) is equivalent to the standard definition of degeneracy.
  • No hidden assumptions: the proof uses only basic graph theory (minimum degree reduction and greedy tree embedding).

6) FINAL

UNRESOLVED. The full conjecture for all $r\ge 2$ remains open, but the base case $r=1$ is proved.
  1. (i) Strongest fully proved partial result obtained:
    • Conjecture holds for $r=1$ (forests): $\mathrm{ex}(n,H)\le (|V(H)|-2)n$ (Theorem thm:146-r1).
    • (From the literature) general bound $\mathrm{ex}(n,H)=O(n^{2-1/(4r)})$ for $r$-degenerate bipartite $H$ (Alon--Krivelevich--Sudakov 2003), and sharp $\mathrm{ex}(n,H)=O(n^{2-1/r})$ for large families (e.g. $r$-degenerate blow-ups of trees).
  2. (ii) Exact first gap: I do not have a proof (or counterexample) for the conjectured exponent $2-1/r$ for general bipartite $r$-degenerate graphs when $r\ge 2$.
  3. (iii) Top 3 next moves:
    1. Strengthen DRC-type lemmas to produce larger structured bipartite subgraphs that support embedding of any $r$-degenerate $H$ with the optimal exponent.
    2. Develop supersaturation and counting of "degenerate" copies (as in the blow-up-of-trees results) for wider classes of $r$-degenerate graphs.
    3. Investigate potential counterexamples via constructions from algebraic graph theory / random algebraic methods, targeting $H$ with high "complexity" but still bounded degeneracy.
  4. (iv) What a minimal counterexample would likely look like: a bipartite $r$-degenerate graph $H$ with bounded average degree but structured so that known embedding/counting arguments fail (e.g. forcing many "degenerate" partial embeddings), together with an explicit $H$-free construction achieving $\Omega(n^{2-1/r+\delta})$ edges.

7) COMPLETION ESTIMATE

9/10. The conjecture is central and has resisted existing general techniques; resolving it likely requires a new conceptual breakthrough or a definitive counterexample.