Reused writeup on Math-5837 (gpt pro 5.2)

Erdős Problem 713 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/713

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/713.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/713.tex.

1) “FORMAL RESTATEMENT”

Let $G$ be a fixed finite bipartite graph. For each $n\in\mathbb N$, let $\mathrm{ex}(n;G)$ be the maximum number of edges in an $n$-vertex (simple) graph $H$ with no subgraph isomorphic to $G$.

Question: Does there always exist an exponent $\alpha\in[1,2)$ and a constant $c>0$ such that \[ \mathrm{ex}(n;G) \sim c\,n^{\alpha}\qquad (n\to\infty)? \] Must such an $\alpha$ be rational?

Edge cases: if $G$ is a single edge, then $\mathrm{ex}(n;G)=0$ for all $n$, so no asymptotic with $c>0$ is possible; thus the question is only meaningful for bipartite $G$ with at least two edges.

2) “QUICK LITERATURE/CONTEXT CHECK”

Only what is explicitly stated in the problem text:

- Erdős initially conjectured that for bipartite $G$ one would have $\mathrm{ex}(n;G)\sim c n^{\alpha}$ with $\alpha$ of the form $1+\frac1k$ or $2-\frac1k$; this was disproved by Erdős--Simonovits $1970$. - For hypergraphs, the analogous statement is false (Frankl--Füredi; simplified by Füredi--Gerbner), but it remains open for graphs.

Per integrity rules, I do not use any other literature results.

3) “ATTACK PLAN”

Proof track: identify classes of bipartite graphs $G$ for which one can prove an asymptotic $\mathrm{ex}(n;G)\sim c n^{\alpha}$, at least for some rational $\alpha$.

Disproof track: try to construct a bipartite $G$ for which $\mathrm{ex}(n;G)$ oscillates between two different power laws or lacks a limit when normalized by $n^{\alpha}$.

Here I provide fully proved results for two basic bipartite families (stars and trees) and small brute-force checks, but no resolution of the general question.

4) “WORK”

FAST REALITY CHECK (small cases).

For the star $K_{1,3}$ (one center, three leaves), any $K_{1,3}$-free graph has maximum degree at most $2$, hence at most $n$ edges. The cycle $C_n$ has maximum degree $2$ and exactly $n$ edges, so for all $n\ge 3$, \[ \mathrm{ex}(n;K_{1,3})=n. \] By brute force over all graphs on $n\le 7$ vertices, I verified: \[ \mathrm{ex}(4;K_{1,3})=4,\ \mathrm{ex}(5;K_{1,3})=5,\ \mathrm{ex}(6;K_{1,3})=6,\ \mathrm{ex}(7;K_{1,3})=7. \]

Proposition 1 (Sharp linear asymptotics for stars). Fix $t\ge 2$ and let $G=K_{1,t}$ be the star with $t$ leaves. Then for every $n$, \[ \mathrm{ex}(n;K_{1,t})\le \min\left\{\binom{n}{2},\ \frac{(t-1)n}{2}\right\}. \] Moreover, for every $n$, \[ \mathrm{ex}(n;K_{1,t})\ge \frac{(t-1)n}{2}-\frac{t^2}{8}. \] In particular, for fixed $t$, \[ \mathrm{ex}(n;K_{1,t})=\frac{t-1}{2}n+O_t(1)\sim \frac{t-1}{2}n \qquad (n\to\infty), \] so the property in the question holds for this $G$ with $\alpha=1$ and $c=(t-1)/2$.

Proof. Upper bound. If a graph $H$ contains no $K_{1,t}$, then no vertex can have degree $\ge t$ (otherwise that vertex together with $t$ of its neighbors forms a $K_{1,t}$). Hence $\Delta(H)\le t-1$ and \[ 2|E(H)|=\sum_{v\in V(H)} \deg(v) \le (t-1)n, \] so $|E(H)|\le \frac{(t-1)n}{2}$. Also trivially $|E(H)|\le \binom{n}{2}$. Taking the maximum over all $K_{1,t}$-free $H$ gives $\mathrm{ex}(n;K_{1,t})\le \min\{\binom{n}{2},\frac{(t-1)n}{2}\}.$

Lower bound / construction. Write $n=qt+r$ with $0\le r<t$. Consider the disjoint union of $q$ copies of the clique $K_t$ plus one clique $K_r$ on the remaining $r$ vertices (if $r\le 1$ this last term contributes no edges). Every vertex has degree at most $t-1$, so the graph is $K_{1,t}$-free. Its number of edges is \[ q\binom{t}{2}+\binom{r}{2} = q\frac{t(t-1)}{2}+\frac{r(r-1)}{2}. \] Compare this with $\frac{(t-1)n}{2}$: \[ \frac{(t-1)n}{2}=\frac{(t-1)(qt+r)}{2}=q\frac{t(t-1)}{2}+\frac{(t-1)r}{2}. \] The difference is \[ \frac{(t-1)r}{2}-\binom{r}{2}=\frac{(t-1)r}{2}-\frac{r(r-1)}{2}=\frac{r(t-r)}{2}. \] Since $0\le r<t$, the product $r(t-r)$ is maximized at $r=t/2$ and in all cases satisfies $r(t-r)\le t^2/4$. Therefore \[ q\binom{t}{2}+\binom{r}{2} \ge \frac{(t-1)n}{2}-\frac{t^2}{8}. \] Thus $\mathrm{ex}(n;K_{1,t})\ge \frac{(t-1)n}{2}-\frac{t^2}{8}$.

Combining the upper and lower bounds yields $\mathrm{ex}(n;K_{1,t})=\frac{t-1}{2}n+O_t(1)$ and hence the asymptotic statement. $\square$

Proposition 2 (Linear upper bound for any fixed tree). Let $T$ be a fixed tree with $t:=|E(T)|\ge 1$ edges. Then for every $n$, \[ \mathrm{ex}(n;T) \le t\,n. \] In particular, for any bipartite tree $T$ the growth exponent is $\alpha=1$ (though this bound does not identify the best constant).

Proof. We use two standard facts, proved here.

Claim 2.1 (Subgraph with large minimum degree). If a graph $H$ on $n$ vertices has average degree $\bar d:=2|E(H)|/n$, then $H$ contains a (nonempty) subgraph $H'$ with minimum degree \[ \delta(H')\ge \bar d/2. \] Proof of Claim 2.1. Iteratively delete vertices of degree $<\bar d/2$ together with their incident edges. Each deleted vertex removes fewer than $\bar d/2$ edges. If all vertices were deleted, the total number of edges removed would be $< n\cdot(\bar d/2)=|E(H)|$, impossible. Hence the process stops with a nonempty subgraph $H'$ in which every remaining vertex has degree at least $\bar d/2$. $\square$

Claim 2.2 (Embedding a tree in high minimum degree). If a graph $H'$ has minimum degree $\delta(H')\ge t$, then $H'$ contains $T$ as a subgraph. Proof of Claim 2.2. Root $T$ at any vertex and order its vertices in a breadth-first order $v_1,\dots,v_{t+1}$ such that each $v_j$ ($j>1$) has a unique parent among $v_1,\dots,v_{j-1}$. We greedily embed vertices one by one into $H'$. Choose any vertex of $H'$ as the image of $v_1$. Suppose we have embedded $v_1,\dots,v_{j-1}$ injectively so that all required edges among them are present. Let $v_j$ have parent $v_p$ with $p<j$. The image of $v_p$ has at least $t$ neighbors in $H'$. At step $j$, fewer than $t$ vertices of $H'$ are already used (since we have used $j-1\le t$ vertices). Therefore among the neighbors of the image of $v_p$ there exists at least one unused vertex; map $v_j$ to such a vertex. This preserves injectivity and ensures the parent-child edge is present. Proceed until all $t+1$ vertices are embedded. $\square$

Now prove the proposition. Let $H$ be an $n$-vertex graph with more than $t n$ edges. Then its average degree is $\bar d>2t$. By Claim 2.1, $H$ has a subgraph $H'$ with minimum degree $\delta(H')\ge \bar d/2>t$. By Claim 2.2, $H'$ (hence $H$) contains $T$. Therefore any $T$-free graph has at most $t n$ edges, i.e. $\mathrm{ex}(n;T)\le t n$. $\square$

5) “VERIFICATION”

- Proposition 1: upper bound uses $\Delta(H)\le t-1$ and the handshake lemma; lower bound uses a disjoint union of cliques $K_t$ and computes the deficit $\frac{r(t-r)}{2}\le t^2/8$, yielding $\mathrm{ex}(n;K_{1,t})=\frac{t-1}{2}n+O_t(1)$. - Proposition 2: both claims were proved explicitly; the greedy embedding uses only that at each step we need one new neighbor and at most $t$ vertices are already used. - Small computation for $K_{1,3}$: brute force confirmed the exact values for $n\le 7$.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result here: for stars $K_{1,t}$ we proved the sharp linear asymptotic $\mathrm{ex}(n;K_{1,t})=\frac{t-1}{2}n+O_t(1)\sim \frac{t-1}{2}n$ (and for $t=3$ we even have the exact value $\mathrm{ex}(n;K_{1,3})=n$ for all $n\ge 3$). For any fixed tree $T$ with $t$ edges, $\mathrm{ex}(n;T)\le t n$ (so again growth is at most linear).

(ii) First gap (crisp statement): given an arbitrary fixed bipartite graph $G$ with at least two edges, prove or disprove the existence of $\alpha\in[1,2)$ and $c>0$ such that \[ \mathrm{ex}(n;G) \sim c\,n^{\alpha}. \]

(iii) Top 3 next moves (concrete targets):

1. Identify a specific bipartite $G$ (beyond trees/stars) for which one can rigorously prove $\mathrm{ex}(n;G)\sim c n^{\alpha}$ with explicit $c,\alpha$ from first principles.

2. Attempt to prove that for each bipartite $G$, the limit of $\log \mathrm{ex}(n;G)/\log n$ exists (even if $\mathrm{ex}(n;G)/n^{\alpha}$ does not), which would at least establish a well-defined exponent.

3. Search computationally for small bipartite graphs $G$ (say up to 8 vertices) and compute $\mathrm{ex}(n;G)$ for $n\le 10$ to look for irregular scaling that might hint at non-existence of a single power law.

(iv) Minimal counterexample structure (if the statement is false): a bipartite graph $G$ for which extremal constructions alternate between two qualitatively different families at different $n$ (causing the normalized quantity $\mathrm{ex}(n;G)/n^{\alpha}$ to oscillate), or for which the correct growth involves additional slowly varying factors (e.g. $n^{\alpha}(\log n)^{\beta}$) that cannot be absorbed into $n^{o(1)}$ while keeping $c>0$.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.