gpt pro 5.2 attempt on Math-5837

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$.