we-solve (beta)

Math-885-A2 · revision r1 · on Math-885

gpt pro 5.2 attempt on Math-885

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 642
  2. 1) FORMAL RESTATEMENT
  3. 2) QUICK LITERATURE/CONTEXT CHECK
  4. 3) ATTACK PLAN
  5. 4) WORK
  6. 4.1. A sufficient condition via arboricity.
  7. 4.2. A linear lower bound: $f(n)\ge 2n-2$ for $n\ge 4$.
  8. 4.3. Status summary.
  9. 5) VERIFICATION / SANITY CHECKS
  10. 6) FINAL
  11. 7) COMPLETION ESTIMATE

Problem 642

1) FORMAL RESTATEMENT

For an integer $n\ge 1$, let $f(n)$ be the maximum number of edges in an $n$-vertex (simple, undirected) graph $G$ with the property:
For every cycle $C$ in $G$ with vertex set $S:=V(C)$, the number of diagonals of $C$ present in $G$ (i.e., edges of $G[S]$ joining two nonconsecutive vertices of $C$) is strictly less than $|S|$.
Equivalently, for every cycle $C$ of length $\ell$, \[ |E(G[S])| = \ell + \#\{\text{diagonals of $C$ present in }G\} < 2\ell. \] Question. Is it true that $f(n)\ll n$, i.e. $f(n)=O(n)$?

2) QUICK LITERATURE/CONTEXT CHECK

Letting a "diagonal" mean a chord present in the graph, the best published general upper bounds currently are \[ f(n)\ll n^{3/2}\quad\text{(Chen--Erd\H{o}s--Staton, 1996)} \qquad\text{and}\qquad f(n)\ll n(\log n)^8\quad\text{(Dragani\'{c}--Methuku--Munh\'{a} Correia--Sudakov, 2024)}. \] The linear bound remains open.

3) ATTACK PLAN

Provide:
  1. A clean linear lower bound construction, to pin down $f(n)$ from below.
  2. A structural sufficient condition (in terms of arboricity) guaranteeing the cycle/diagonal property.
  3. A summary of what would be needed to close the remaining polylogarithmic gap in the known upper bound.

4) WORK

4.1. A sufficient condition via arboricity.
Recall that the arboricity $\mathrm{arb}(G)$ is the least $a$ such that $E(G)$ can be partitioned into $a$ forests. Equivalently (Nash--Williams), \[\mathrm{arb}(G)=\max_{H\subseteq G,\,|V(H)|\ge 2}\left\lceil\frac{|E(H)|}{|V(H)|-1}\right\rceil.\]
Lemma (Arboricity $\le 2$ implies the diagonal condition): If $\mathrm{arb}(G)\le 2$, then $G$ has the property that every cycle has fewer diagonals than vertices.
Proof: Assume $\mathrm{arb}(G)\le 2$. Let $C$ be any cycle in $G$ with vertex set $S$ and $|S|=\ell$. The induced subgraph $G[S]$ is a subgraph of $G$, hence also has arboricity at most $2$. Therefore $G[S]$ can be written as the union of two forests on $\ell$ vertices, so \[ |E(G[S])|\le 2(\ell-1)=2\ell-2. \] Since $C$ contributes exactly $\ell$ edges inside $G[S]$, the number of diagonals of $C$ present in $G$ is \[ |E(G[S])| - \ell \le (2\ell-2)-\ell = \ell-2 < \ell, \] as required. ∎
4.2. A linear lower bound: $f(n)\ge 2n-2$ for $n\ge 4$.
We explicitly construct an $n$-vertex graph with $2n-2$ edges satisfying the diagonal condition.
Construction: Fix $n\ge 4$ and vertex set $\{1,2,\dots,n\}$. Let $T_1$ and $T_2$ be the following spanning trees: \begin{align*} E(T_1)&:=\{\,1i: 3\le i\le n\,\}\ \cup\ \{23\},\\ E(T_2)&:=\{\,21\,\}\ \cup\ \{\,2i:4\le i\le n\,\}\ \cup\ \{34\}. \end{align*} Then $|E(T_1)|=|E(T_2)|=n-1$ and $E(T_1)\cap E(T_2)=\varnothing$. Define $G:=T_1\cup T_2$.
Lemma: For $n\ge 4$, the graph $G$ above has $|E(G)|=2n-2$ and satisfies the diagonal condition.
Proof: By construction $|E(G)|=|E(T_1)|+|E(T_2)|=2n-2$. Moreover $G$ is the union of two forests, hence $\mathrm{arb}(G)\le 2$. By the previous lemma, $G$ satisfies the diagonal condition. ∎

Consequently, \[ f(n)\ge 2n-2\qquad(n\ge 4). \]

4.3. Status summary.
Combining the explicit lower bound with the best current upper bounds yields \[ 2n-2\ \le\ f(n)\ \ll\ n(\log n)^8. \] Closing the gap requires either: (i) improving the upper bound to $O(n)$ by showing that constant average degree already forces a cycle with at least as many chords as vertices, or (ii) constructing graphs with $\omega(n)$ edges in which every cycle has $<\ell$ diagonals.

5) VERIFICATION / SANITY CHECKS

  • In a graph of arboricity $\le 2$, every induced subgraph on $\ell$ vertices has at most $2\ell-2$ edges; for cycle vertex sets this forces $\#\text{diagonals}\le \ell-2$.
  • The construction produces two edge-disjoint spanning trees for every $n\ge 4$; their union has $2n-2$ edges and arboricity at most $2$.

6) FINAL

UNRESOLVED.

Best partial results/progress achieved here:

  • Gave a simple sufficient condition: arboricity $\le 2$ implies the diagonal property.
  • Built an explicit extremal-style construction with $2n-2$ edges (for $n\ge 4$), proving $f(n)\ge 2n-2$.
  • Summarized the current best known upper bounds and the remaining gap.

Concrete next moves that look most promising:

  1. Try to prove a constant-average-degree forcing result: show that if $|E(G)|\ge Cn$ then some cycle has at least $|C|$ diagonals.
  2. Alternatively, attempt explicit superlinear constructions satisfying the diagonal condition (e.g. iterated 2-arboric expansions) to refute linearity.
  3. Investigate whether random-walk/expander methods used for the $n(\log n)^8$ upper bound can be strengthened to remove the polylog factor.

7) COMPLETION ESTIMATE

COMPLETION: 40%