Erdős Problem #766

Problem 766 (Round 2)

1) ROUND-2 OBJECTIVE

I pursue (C) obstruction/correction. The exact function $f(n;k,l)$ is still open, but Round 1 left its most important heuristic unproved: that the minimiser should be bipartite. The best Round-2 step is therefore to turn this heuristic into a theorem, thereby reducing the problem asymptotically to a finite family of bipartite graphs and solving the endpoint case $l=\lfloor k^2/4\rfloor$ exactly for large $n$.

2) Round-1 FOUNDATION USED

I use the following Round-1 facts.

• For $a:=\min\{t: l\le t(k-t)\}$ one has \[ f(n;k,l)\le \mathrm{ex}(n;K_{a,k-a})=O\left(n^{2-1/a}\right). \]
• Since $l\le \lfloor k^2/4\rfloor$, there exists at least one bipartite graph on $k$ vertices and $l$ edges.

Round 1 stated that one expects the minimiser to be bipartite; Round 2 proves that this is correct for all sufficiently large $n$.

3) NEW INSIGHT / TOOL (ROUND-2)

The new tool is the Erdős--Stone--Simonovits theorem. It implies that every fixed non-bipartite graph $H$ has \[ \mathrm{ex}(n;H)=\Theta(n^2). \] But Round 1 already supplied a bipartite $k$-vertex $l$-edge graph $B$ with \[ \mathrm{ex}(n;B)=O\left(n^{2-1/a}\right)=o(n^2). \] Therefore, for fixed $(k,l)$ in the range $k<l\le \lfloor k^2/4\rfloor$, every asymptotic minimiser for $f(n;k,l)$ must be bipartite.

This immediately yields an exact endpoint identification when $l=\lfloor k^2/4\rfloor$: among bipartite graphs on $k$ vertices, the only graph with that many edges is the balanced complete bipartite graph $K_{\lfloor k/2\rfloor,\lceil k/2\rceil}$.

4) ATTACK PLAN (ROUND-2)

The exact Round-1 gap was:

"The minimiser should be bipartite" was only heuristic.

I close that gap in three steps.

1. Use Erdős--Stone--Simonovits to show every non-bipartite candidate has quadratic extremal number.
2. Use the Round-1 Kővári--Sós--Turán upper bound to produce one bipartite candidate with subquadratic extremal number.
3. Because there are only finitely many $k$-vertex $l$-edge graphs, conclude that for sufficiently large $n$ the minimum is attained inside the bipartite subfamily.

Then I treat the endpoint $l=\lfloor k^2/4\rfloor$ by a direct uniqueness argument.

5) WORK (ROUND-2)

For fixed integers $k,l$ with $k<l\le \lfloor k^2/4\rfloor$, let \[ \mathcal G_{k,l}:=\{G: |V(G)|=k,\ |E(G)|=l\} \] and let $\mathcal B_{k,l}\subseteq \mathcal G_{k,l}$ be the bipartite members.

Lemma 5.1.

For every fixed non-bipartite graph $H$, \[ \mathrm{ex}(n;H)=\left(1-\frac{1}{\chi(H)-1}+o(1)\right)\frac{n^2}{2}. \] In particular, if $\chi(H)\ge 3$, then \[ \mathrm{ex}(n;H)=\Theta(n^2). \]

Justification. This is the Erdős--Stone--Simonovits theorem.

Lemma 5.2.

There exists $B\in \mathcal B_{k,l}$ such that \[ \mathrm{ex}(n;B)=o(n^2). \]

Proof. By the assumption $l\le \lfloor k^2/4\rfloor$, there exists a bipartite graph on $k$ vertices with $l$ edges. More concretely, by the Round-1 construction there is some $a\in\{1,\dots,\lfloor k/2\rfloor\}$ with $l\le a(k-a)$ and a graph $B\subseteq K_{a,k-a}$ having $k$ vertices and $l$ edges. Then \[ \mathrm{ex}(n;B)\le \mathrm{ex}(n;K_{a,k-a})=O\left(n^{2-1/a}\right)=o(n^2) \] by the Kővári--Sós--Turán theorem. $\square$

Theorem 5.3 (asymptotic bipartite reduction).

For every fixed $k,l$ with $k<l\le \lfloor k^2/4\rfloor$, there exists $N=N(k,l)$ such that for all $n\ge N$, \[ f(n;k,l)=\min\{\mathrm{ex}(n;B): B\in \mathcal B_{k,l}\}. \] In words: for sufficiently large $n$, the minimisation defining $f(n;k,l)$ may be restricted to bipartite graphs.

Proof. By definition, \[ f(n;k,l)=\min\{\mathrm{ex}(n;G): G\in \mathcal G_{k,l}\}. \] Let \[ M_B(n):=\min\{\mathrm{ex}(n;B): B\in \mathcal B_{k,l}\}. \] Clearly $f(n;k,l)\le M_B(n)$.

Now fix any non-bipartite graph $H\in \mathcal G_{k,l}\setminus \mathcal B_{k,l}$. By Lemma 5.1, \[ \mathrm{ex}(n;H)=\Theta(n^2). \] By Lemma 5.2, there exists some bipartite $B\in \mathcal B_{k,l}$ with \[ \mathrm{ex}(n;B)=o(n^2). \] Hence for each fixed non-bipartite $H$ there exists $N_H$ such that \[ \mathrm{ex}(n;B)<\mathrm{ex}(n;H)\qquad\text{for all }n\ge N_H. \] Since $\mathcal G_{k,l}\setminus \mathcal B_{k,l}$ is finite, taking \[ N:=\max_H N_H \] over all non-bipartite $H\in \mathcal G_{k,l}\setminus \mathcal B_{k,l}$ shows that for every $n\ge N$, every non-bipartite candidate has larger extremal number than some bipartite candidate. Therefore the minimum is attained within $\mathcal B_{k,l}$, i.e. \[ f(n;k,l)=M_B(n)=\min\{\mathrm{ex}(n;B): B\in \mathcal B_{k,l}\}. \] $\square$

Corollary 5.4.

For fixed $k,l$ in the stated range, \[ f(n;k,l)=o(n^2). \]

Proof. Immediate from Theorem 5.3 and Lemma 5.2. $\square$

Theorem 5.5 (endpoint $l=\lfloor k^2/4\rfloor$).

For fixed $k$ and sufficiently large $n$, \[ f\left(n;k,\lfloor k^2/4\rfloor\right)=\mathrm{ex}\left(n;K_{\lfloor k/2\rfloor,\lceil k/2\rceil}\right). \]

Proof. By Theorem 5.3, for sufficiently large $n$ the minimum may be taken over bipartite graphs with $k$ vertices and $\lfloor k^2/4\rfloor$ edges. But by Mantel's theorem, a bipartite graph on $k$ vertices has at most $\lfloor k^2/4\rfloor$ edges, with equality only for the balanced complete bipartite graph \[ K_{\lfloor k/2\rfloor,\lceil k/2\rceil}. \] Therefore the bipartite family $\mathcal B_{k,\lfloor k^2/4\rfloor}$ consists of this single graph, and the displayed identity follows. $\square$

What remains open after Round 2.

The strict monotonicity question is now sharply reduced: for fixed $k$ and large $n$, it is entirely a question about comparing extremal numbers of finitely many bipartite graphs on $k$ vertices. In particular, no non-bipartite graph can be asymptotically extremal in the minimisation problem.

6) ADVERSARIAL VERIFICATION

• Does Theorem 5.3 hold for all $n$? No. The argument is asymptotic, since it compares $\Theta(n^2)$ with $o(n^2)$. So the conclusion is correctly stated only for sufficiently large $n$.
• Could a non-bipartite graph have smaller extremal number than a bipartite one for small $n$? Yes, in principle. That is why the theorem includes the threshold $N(k,l)$.
• Why is finiteness important? Because the set of $k$-vertex $l$-edge graphs is finite, one can take the maximum of the finitely many thresholds $N_H$.
• Is the endpoint uniqueness claim correct? Yes. Among all bipartite graphs on $k$ vertices, the maximum possible number of edges is $\lfloor k^2/4\rfloor$, attained uniquely by the balanced complete bipartite graph.
• Did Round 2 solve monotonicity? No. It only localises the monotonicity problem to the finite bipartite family, which is a strict structural advance but not a full solution.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED). Round 2 proves the key structural correction that Round 1 only conjectured: for every fixed $k,l$ with $k<l\le \lfloor k^2/4\rfloor$, the minimiser in the definition of $f(n;k,l)$ is asymptotically bipartite. Moreover, \[ f\left(n;k,\lfloor k^2/4\rfloor\right)=\mathrm{ex}\left(n;K_{\lfloor k/2\rfloor,\lceil k/2\rceil}\right) \] for all sufficiently large $n$. This reduces the remaining difficulty to a finite comparison problem inside the bipartite regime.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 35%

9) REFERENCES

• Erdős Problem #766, statement and historical note (official problem page).
• Erdős--Stone--Simonovits theorem.
• Kővári--Sós--Turán theorem.
• Mantel's theorem.

10) OUTPUT FORMAT

Here the Erdős problem number is $x=766$.

Problem 766: the two possible families immediately below the endpoint

1) OBJECTIVE AND SOURCE REVIEW

Attempt dated 2026-09-23. I read the complete 766.tex. It defines $f(n;k,l)=\min_{|V(H)|=k,|E(H)|=l}\operatorname{ex}(n;H)$ and leaves the strict monotonicity question in $l$ unresolved. Its eventual bipartite reduction and balanced endpoint do not evaluate the underlying extremal numbers. I classify the candidates one edge below that endpoint and simplify the reduction without an Erdős--Stone input.

2) WORK

Every nonbipartite $H$ is avoided by the balanced complete bipartite graph, so \[ \operatorname{ex}(n;H)\ge\lfloor n^2/4\rfloor \] uniformly, without a graph-dependent threshold. There is a bipartite candidate $B$ whenever $l\le\lfloor k^2/4\rfloor$, and $B\subseteq K_{k,k}$. An elementary common-neighbour count gives $\operatorname{ex}(n;K_{k,k})=O_k(n^{2-1/k})$: in a $K_{k,k}$-free graph, \[ \sum_v\binom{d(v)}k\le(k-1)\binom nk. \] Indeed every $k$-vertex set has at most $k-1$ common neighbours. The inequality $\binom dk\ge(d-k+1)_+^k/k!$ and convexity bound the average degree by $(k-1)^{1/k}n^{1-1/k}+k-1$. Thus the fixed bipartite candidate eventually beats every nonbipartite candidate simultaneously. This reproves the needed reduction directly.

Let $k=2r$, $r\ge3$, and $l=r^2-1$. In a bipartite candidate with parts of sizes $a,2r-a$, we need \[ a(2r-a)=r^2-(a-r)^2\ge r^2-1. \] Up to interchanging the sides, either $a=r$ or $a=r-1$. The former graph is $K_{r,r}$ with one edge removed; the latter is the full $K_{r-1,r+1}$. Consequently, for all sufficiently large $n$, \[ f(n;2r,r^2-1)=\min\{\operatorname{ex}(n;K_{r,r}-e), \operatorname{ex}(n;K_{r-1,r+1})\}. \] For $k=2r+1$, $r\ge3$, one edge below the maximum means $l=r(r+1)-1$. An unbalanced split has at most $(r-1)(r+2)=r(r+1)-2$ edges. Only the balanced split survives, giving \[ f(n;2r+1,r(r+1)-1)=\operatorname{ex}(n;K_{r,r+1}-e) \] eventually. Edge transitivity makes the choice of deleted edge immaterial.

3) ADVERSARIAL VERIFICATION

These are exact identifications with other extremal functions, not numerical evaluations of those functions. Isolated vertices do not create extra candidates: every bipartition must still have capacity at least $l$, and the near-maximum edge count forces the listed graphs. Ordinary non-strict monotonicity follows by deleting an edge from an $(l+1)$-edge minimizer; strict inequality does not follow from graph containment alone.

4) FINAL

UNRESOLVED. The first layer below the endpoint reduces to one or two explicit extremal numbers. Their necessary strict comparisons, and the general strict-monotonicity question, remain unproved.

5) SOURCES CHECKED

The complete supplied 766.tex, read 2026-09-23. The bipartite reduction, common-neighbour estimate, and near-endpoint classification are proved here and require no uninspected external theorem.

6) COMPLETION ESTIMATE

Subjective progress toward the strict-monotonicity problem. COMPLETION: 15%

Problem 766

1) FORMAL RESTATEMENT

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

For integers $k,l$ with $0\le l\le \binom{k}{2}$ define \[ f(n;k,l):=\min\{\mathrm{ex}(n;G): v(G)=k,\ e(G)=l\}. \] The task is to estimate $f(n;k,l)$ for $k<l\le k^2/4$, and to ask whether for fixed $k$ and large $n$ the function $l\mapsto f(n;k,l)$ is strictly monotone.

2) QUICK LITERATURE/CONTEXT CHECK

As recorded in the original sources and on later compilations, Dirac and Erdős proved independently that for \[l=\lfloor k^2/4\rfloor+1\quad\text{one has}\quad f(n;k,l)\le \lfloor n^2/4\rfloor+1. \] I did not locate a complete resolution for the full range $k<l\le k^2/4$.

3) ATTACK PLAN

A standard approach is to compare $G$ to complete bipartite graphs and apply the Kővári--Sós--Turán (KST) upper bound. Since $l\le k^2/4$ guarantees the existence of bipartite $k$-vertex graphs with $l$ edges, for fixed $k$ and large $n$ one expects the minimiser for $f(n;k,l)$ to be bipartite (hence $f(n;k,l)=o(n^2)$). To go beyond crude bounds one needs to identify, among all $k$-vertex $l$-edge graphs, those with the smallest extremal number.

4) WORK

A general constructive upper bound via KST.

Fix $k$ and $l\le k^2/4$. Let $a\in\{1,2,\dots,\lfloor k/2\rfloor\}$ be the smallest integer such that \[ l\le a(k-a). \] Then there exists a bipartite graph $G$ on $k$ vertices with $l$ edges that is a subgraph of $K_{a,k-a}$. Since $G\subseteq K_{a,k-a}$, any $K_{a,k-a}$-free graph is also $G$-free, hence \[ \mathrm{ex}(n;G)\le \mathrm{ex}(n;K_{a,k-a}). \] Therefore \[ f(n;k,l)\le \mathrm{ex}(n;K_{a,k-a}). \] By the Kővári--Sós--Turán theorem (for fixed $a$ and $b=k-a$), \[ \mathrm{ex}(n;K_{a,b})\le (b-1)^{1/a} n^{2-1/a} + \frac{a-1}{2}n. \] Consequently, for fixed $k,l$ we obtain the explicit asymptotic upper bound \[ f(n;k,l)=O\big(n^{2-1/a}\big),\qquad a=\min\{t: l\le t(k-t)\}. \] In particular, if $l$ is close to the maximum $k^2/4$, then $a\approx k/2$ and the exponent is $2-2/k$.

Trivial universal lower bound.

Since $l>k$ implies every such $G$ contains a cycle, any tree on $n$ vertices is $G$-free; hence \[ \mathrm{ex}(n;G)\ge n-1\quad\text{for every }G\text{ in the minimisation, so}\quad f(n;k,l)\ge n-1. \] This bound is far from sharp in most regimes.

Heuristic for monotonicity.

Increasing $l$ increases the edge-density of the forbidden graph class, but the minimisation ranges over all $k$-vertex graphs with exactly $l$ edges; it is not clear that the minimiser changes monotonically with $l$. Even if $f(n;k,l)$ is nondecreasing in $l$ for large $n$ (a plausible guess), strict monotonicity would require showing that no two edge-counts share the same asymptotically extremal obstruction, which seems delicate.

5) OBSTRUCTIONS/CAVEATS

• Sharp lower bounds on $f(n;k,l)$ require showing that every $k$-vertex $l$-edge graph has extremal number at least some quantity. This is hard because the minimiser could be a very special sparse-in-structure bipartite graph.
• Determining strict monotonicity in $l$ would likely require identifying the extremal graph(s) $G$ achieving the minimum, for each $l$, at least asymptotically.

6) FINAL

UNRESOLVED.

• (i) Where I got stuck: I did not determine the correct asymptotic order of $f(n;k,l)$ for the full range nor settle strict monotonicity.
• (ii) Partial progress: I derived an explicit KST-based upper bound $f(n;k,l)=O(n^{2-1/a})$ with $a$ determined by $l\le a(k-a)$, and recorded the trivial universal lower bound $n-1$.
• (iii) What seems next: Improve lower bounds by relating any $k$-vertex $l$-edge graph to a forced bipartite substructure (e.g. a fixed $K_{s,t}$, theta graph, or even cycle) whose extremal number is well understood; then optimise over which such substructures must appear as a function of $k,l$.
• (iv) Best guess: For fixed $k$ and large $n$, the minimiser should be bipartite; the correct exponent likely depends on the smallest $s$ for which some $K_{s,t}$-type configuration is unavoidable in all $k$-vertex $l$-edge graphs.

7) COMPLETION ESTIMATE

$10\%$.