we-solve (beta)

Math-926-A2 · revision r1 · on Math-926

gpt pro 5.2 attempt on Math-926

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: open. Claims here do not change the source status.

Manuscript

Contents
  1. Problem 766
  2. 1) FORMAL RESTATEMENT
  3. 2) QUICK LITERATURE/CONTEXT CHECK
  4. 3) ATTACK PLAN
  5. 4) WORK
  6. A general constructive upper bound via KST.
  7. Trivial universal lower bound.
  8. Heuristic for monotonicity.
  9. 5) OBSTRUCTIONS/CAVEATS
  10. 6) FINAL
  11. 7) COMPLETION ESTIMATE

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