Erdős Problem #571

Erdős Problem 571

Statement and scope.

Exponent one.

Exponent three halves: upper bound.

Exponent three halves: lower bound for every large order.

For any sufficiently large $n$, choose the largest power of two with $q\leq\sqrt{n/2}$. Then $q>\sqrt{n/2}/2$. Add isolated vertices to reach order $n$; the result has more than $n^{3/2}/(16\sqrt2)$ edges. Together with $1$, this proves \[ \operatorname{ex}(n,C_4)=\Theta(n^{3/2}). \tag{2} \] The choice of $q$ is necessary to obtain every large $n$, rather than only a sparse subsequence.

An arithmetic closure calculation.

This calculation is only arithmetic. To turn it into a solution one would need a proved graph operation that sends a graph or suitable rooted construction of parameter $x$ to one of parameter $\Phi_j(x)$, while preserving both matching extremal estimates and the requirement of a single forbidden graph. An identity between rational numbers supplies none of those properties. No such closure lemma is proved here.

Source and assessment.

Completion rate estimate: 35%.

1) FORMAL RESTATEMENT

For a fixed graph $G$, let $\ex(n;G)$ denote the maximum number of edges in an $n$-vertex graph containing no copy of $G$ as a (not necessarily induced) subgraph.

Question: For every rational number $\alpha\in[1,2)$, does there exist a bipartite graph $G$ such that \[ \ex(n;G)=\Theta(n^{\alpha})\qquad\text{as }n\to\infty? \] (Here $\Theta$ hides positive multiplicative constants depending on $G$.)

2) QUICK LITERATURE/CONTEXT CHECK

The problem statement notes:

- Erdős conjectured that for bipartite $G$ we have $\ex(n;G)\sim c\,n^{\alpha}$ for some $c>0$ and some rational $\alpha$ of the special forms $1+1/k$ or $2-1/k$.

- There are known examples of various rational exponents, and Bukh--Conlon showed the weaker statement that every rational $\alpha\in[1,2)$ can be achieved by a finite family of forbidden graphs.

(No other external results are used as black boxes below.)

3) ATTACK PLAN

- Produce explicit constructions giving lower bounds $\ex(n;G)\ge c n^{\alpha}$ for chosen bipartite $G$, and complementary upper bounds $\ex(n;G)\le C n^{\alpha}$.

- Try to build "operations" on graphs $G$ (subdivision, blow-up, products) that transform known exponents into new rational exponents.

4) WORK

Fast reality check.

- Exponent $\alpha=1$ is easy: take any fixed tree $T$ (bipartite). Then $\ex(n;T)=\Theta(n)$ (Proposition 571.2).

- Exponent $\alpha=3/2$ is known for $G=C_4$ by Erdős--Klein (as stated in the problem file). Below we give a fully explicit $C_4$-free bipartite construction with $\Omega(n^{3/2})$ edges (Lemma 571.3).

Lemma 571.1 (tree embedding from minimum degree). Let $T$ be a tree on $t\ge 2$ vertices, and let $\Gamma$ be a graph with minimum degree $\delta(\Gamma)\ge t-1$. Then $\Gamma$ contains a copy of $T$.

Proof. We prove by induction on $t$.

Base $t=2$: then $T=K_2$, and $\delta(\Gamma)\ge 1$ implies $\Gamma$ has an edge, i.e. contains $K_2$.

Induction step: assume the claim true for trees on $t-1$ vertices, and let $T$ be a tree on $t$ vertices. Choose a leaf $x\in V(T)$ and let $y$ be its unique neighbour. Let $T'=T-x$ be the tree on $t-1$ vertices obtained by removing $x$.

Since $\delta(\Gamma)\ge t-1 \ge (t-1)-1=t-2$, by the induction hypothesis $\Gamma$ contains a copy of $T'$. Fix an embedding $f:V(T')\hookrightarrow V(\Gamma)$.

We extend $f$ to an embedding of $T$ by mapping $x$ to a new vertex adjacent to $f(y)$. Let $S=f(V(T'))$; then $|S|=t-1$ and $f(y)\in S$. The vertex $f(y)$ has at least $t-1$ neighbours in $\Gamma$. Among these neighbours, at most $|S\setminus\{f(y)\}|=t-2$ are contained in $S$. Therefore $f(y)$ has at least one neighbour $z\notin S$.

Define $f(x)=z$. Then $f$ is injective on $V(T)$ and preserves adjacency (the only new edge is $xy$, which maps to $f(y)f(x)=f(y)z$, an edge by construction). Thus $\Gamma$ contains $T$. $\square$

Proposition 571.2 (trees give exponent $1$). Let $T$ be a fixed tree on $t\ge 2$ vertices. Then for all $n$, \[ \frac{t-2}{2}\,n - O_T(1)\ \le\ \ex(n;T)\ \le\ (t-2)\,n. \] In particular $\ex(n;T)=\Theta(n)$, so $\alpha=1$ is a Turán exponent achieved by a bipartite graph.

Proof. Upper bound. Let $\Gamma$ be an $n$-vertex $T$-free graph. By Lemma 571.1 (contrapositive), $\Gamma$ must have a vertex of degree at most $t-2$. Remove such a vertex and repeat. This produces an ordering of vertices $v_1,\dots,v_n$ such that when $v_i$ is removed it has degree at most $t-2$ in the remaining graph. Counting edges at the moment they are removed, \[ e(\Gamma) \le \sum_{i=1}^n (t-2) = (t-2)n. \] Hence $\ex(n;T)\le (t-2)n$.

Lower bound. Partition the $n$ vertices into disjoint groups of size $t-1$, plus at most one leftover group of size $<t-1$. On each full group place a clique $K_{t-1}$ and put no edges between groups. The resulting graph contains no copy of $T$, since every component has at most $t-1$ vertices, while $T$ has $t$ vertices and is connected. The number of edges is \[ \left\lfloor\frac{n}{t-1}\right\rfloor\binom{t-1}{2} \ge \frac{n-(t-2)}{t-1}\cdot \frac{(t-1)(t-2)}{2} = \frac{t-2}{2}n - O_T(1). \] So $\ex(n;T)\ge \frac{t-2}{2}n - O_T(1)$.

Combining bounds gives $\ex(n;T)=\Theta(n)$. $\square$

Lemma 571.3 (explicit $C_4$-free bipartite graph with $\Omega(n^{3/2})$ edges). Let $q$ be a prime power and let $\mathbb F_q$ be the field with $q$ elements. Consider the incidence structure of the projective plane $\mathrm{PG}(2,q)$:

- Points are $1$-dimensional subspaces of $\mathbb F_q^3$.

- Lines are $2$-dimensional subspaces of $\mathbb F_q^3$.

- A point $P$ is incident to a line $L$ if $P\subseteq L$.

Let $\Gamma_q$ be the bipartite incidence graph with vertex classes $\mathcal P$ (points) and $\mathcal L$ (lines), and edges for incidences.

Then $\Gamma_q$ is $C_4$-free and has \[ |V(\Gamma_q)| = 2(q^2+q+1),\qquad e(\Gamma_q) = (q+1)(q^2+q+1)=\Omega(|V(\Gamma_q)|^{3/2}). \]

Proof. Counts. The number of $1$-dimensional subspaces of $\mathbb F_q^3$ is \[ |\mathcal P|=\frac{q^3-1}{q-1}=q^2+q+1. \] By duality, the number of $2$-dimensional subspaces is the same: $|\mathcal L|=q^2+q+1$. Thus $|V(\Gamma_q)|=2(q^2+q+1)$.

Fix a line $L$ (a $2$-dimensional subspace). The number of $1$-dimensional subspaces contained in $L$ equals the number of points in $\mathrm{PG}(1,q)$, namely $q+1$. (Indeed, a $2$-dimensional vector space has $q^2-1$ nonzero vectors, each $1$-dimensional subspace contributes $q-1$ nonzero vectors, so $(q^2-1)/(q-1)=q+1$.) Therefore every line-vertex in $\Gamma_q$ has degree $q+1$. Since there are $q^2+q+1$ line-vertices, \[ e(\Gamma_q)=|\mathcal L|\cdot(q+1)=(q^2+q+1)(q+1). \]

$C_4$-freeness. A $4$-cycle in the incidence graph would have the form \[ P_1 - L_1 - P_2 - L_2 - P_1, \] where $P_1\neq P_2$ are points and $L_1\neq L_2$ are lines, with each $P_i$ incident to each $L_j$. In geometric terms, this means two distinct lines $L_1$ and $L_2$ are both incident to the same two distinct points $P_1$ and $P_2$.

But in the vector-space model, two distinct points $P_1,P_2$ are two distinct $1$-dimensional subspaces of $\mathbb F_q^3$. Their span $\langle P_1,P_2\rangle$ is a $2$-dimensional subspace, and it is the unique $2$-dimensional subspace containing both $P_1$ and $P_2$. Therefore there is a unique line incident to both points. Hence such a configuration with two distinct lines through two distinct points is impossible, so $\Gamma_q$ contains no $4$-cycle.

Asymptotics. Let $N=|V(\Gamma_q)|=2(q^2+q+1)$. Then $e(\Gamma_q)\asymp q^3$ while $N\asymp q^2$, so $e(\Gamma_q)=\Omega(N^{3/2})$. $\square$

5) VERIFICATION

Numerical sanity check for Lemma 571.3. For $q=2,3,4,5$ the construction yields $(N,e)=(14,21),(26,52),(42,105),(62,186)$ and the ratios $e/N^{3/2}$ are approximately $0.401,0.392,0.386,0.381$, consistent with $e=\Theta(N^{3/2})$.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result here (within this writeup): explicit bipartite examples achieve at least $\alpha=1$ (trees) and $\alpha=3/2$ (via $C_4$; the problem file states the matching upper bound $\ex(n;C_4)\sim c n^{3/2}$).

(ii) First gap (crisp): given an arbitrary rational $\alpha\in[1,2)$, construct a single bipartite graph $G$ and prove matching upper/lower bounds $\ex(n;G)=\Theta(n^{\alpha})$.

(iii) Top 3 next moves:

1. Develop graph operations that predictably transform exponents (e.g. subdivisions, products) and prove corresponding extremal estimates, aiming to generate all rational exponents.

2. For a target rational $\alpha=p/q$, try to design a bipartite "incidence-type" graph whose natural counting suggests $\ex(n;G)\approx n^{\alpha}$, and then prove the matching upper bound by a counting/cycle method.

3. Perform computational experiments for small graphs $G$ (enumerating bipartite graphs up to some size) to empirically estimate $\ex(n;G)$ and guess which $G$ might realise new rational exponents.

(iv) Minimal counterexample structure (if false): a rational $\alpha\in[1,2)$ such that for every bipartite $G$, the function $\ex(n;G)$ either grows like $n^{\beta}$ with $\beta\ne\alpha$, or fails to have a well-defined exponent in the sense $\ex(n;G)=\Theta(n^{\alpha})$.