we-solve (beta)

Math-5404-A7 · revision r1 · on Math-5404

gpt pro 5.4 attempt on Math-5404

No claim recorded · LLM-generated · gpt pro 5.4 ·

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. Erdős--Hajnal reciprocal cycle-length sum (Problem 65) --- Round 5
  2. 1) ROUND-5 OBJECTIVE
  3. 2) Round-4 FOUNDATION USED
  4. 3) NEW INSIGHT / TOOL (ROUND-5)
  5. 4) ATTACK PLAN (ROUND-5)
  6. 5) WORK (ROUND-5)
  7. 5.1. Exact small-order extremal values
  8. 5.2. Uniform extension through $n=22$
  9. 5.3. The $n=23$ case
  10. 5.4. Main Round-5 theorem
  11. 6) ADVERSARIAL VERIFICATION
  12. 7) FINAL (EXACTLY ONE)
  13. 8) COMPLETION ESTIMATE (MANDATORY)
  14. 9) REFERENCES
  15. References

Erdős--Hajnal reciprocal cycle-length sum (Problem 65) --- Round 5

1) ROUND-5 OBJECTIVE

Path chosen: (A) proof-oriented gap closure. Round 4 proved the complete-bipartite minimiser statement on the line \[ |E(G)|=2|V(G)|-4 \] up to $n=13$, with the first unresolved point isolated at $n=14$. In this round I use exact small-order extremal data for forbidden cycle families to push the same line much further. The new goal is:

prove that for every $7\le n\le 23$, among all $n$-vertex graphs with $2n-4$ edges, the minimum of \[ S(G)=\sum_{\ell\in\mathcal C(G)}\frac1\ell \] is $1/4$, attained by $K_{2,n-2}$.
This is the most promising direction because Round 4 had already reduced the problem to controlling graphs with no short cycles, and exact extremal numbers for the forbidden families $\{C_3,C_4,C_5\}$ and $\{C_3,C_4,C_6\}$ are available in the relevant range.

2) Round-4 FOUNDATION USED

I rely on the following vetted Round 4 results as black boxes.

  • $F1$ For $2\le a\le b$, the complete bipartite graph $K_{a,b}$ has \[ \mathcal C(K_{a,b})=\{4,6,\dots,2a\}, \qquad S(K_{a,b})=\sum_{j=2}^a\frac1{2j}=\frac12(H_a-1). \] In particular, \[ S(K_{2,n-2})=\frac14. \]

  • $F2$ Round 3 proved that for every $7\le n\le 12$ and $m=2n-4$, every $n$-vertex $m$-edge graph satisfies $S(G)\ge 1/4$, with equality attained by $K_{2,n-2}$.

  • $F3$ Round 4 proved the next case $(n,m)=(13,22)$: every $13$-vertex $22$-edge graph satisfies $S(G)\ge 1/4$, with equality attained by $K_{2,11}$.

Thus Round 4 already settled the line $m=2n-4$ for all $7\le n\le 13$.

3) NEW INSIGHT / TOOL (ROUND-5)

The new ingredient is the use of exact extremal numbers for small forbidden cycle families. Write \[ \operatorname{ex}(n;\mathcal F) \] for the maximum number of edges in an $n$-vertex graph containing no member of $\mathcal F$. The ANU extremal-graph tables provide the exact values of \[ \operatorname{ex}(n;\{C_3,C_4,C_5\}) \qquad\text{and}\qquad \operatorname{ex}(n;\{C_3,C_4,C_6\}) \] for all $n$ in the range relevant here.

These data give a new uniform mechanism:

  • if $G$ has $2n-4$ edges and no $C_3,C_4$, then comparison with $\operatorname{ex}(n;\{C_3,C_4,C_5\})$ forces a $C_5$ whenever $2n-4$ exceeds that extremal value;
  • similarly, comparison with $\operatorname{ex}(n;\{C_3,C_4,C_6\})$ forces a $C_6$.

This simultaneously settles $14\le n\le 22$. For $n=23$, where $\operatorname{ex}(23;\{C_3,C_4,C_5\})=42$ is exactly the target edge count, the same data identify a unique exceptional graph with no $C_3,C_4,C_5$; an explicit verification on that graph then finishes the case.

4) ATTACK PLAN (ROUND-5)

The exact gap left by Round 4 was the unresolved tail of the $K_{2,n-2}$ line beyond $n=13$.

The plan is:

  1. Use $F2$--$F3$ to reduce to $14\le n\le 23$.
  2. For $14\le n\le 22$, show that any graph with $2n-4$ edges must contain either $C_3$ or $C_4$, or else both $C_5$ and $C_6$.
  3. Handle $n=23$ separately:
    • if a $23$-vertex $42$-edge graph has a $C_5$, then together with a forced $C_6$ we are done;
    • if it has no $C_5$, exact extremal data force it to be the unique published girth-$6$ extremal graph on $23$ vertices and $42$ edges, and that explicit graph contains both a $6$-cycle and an $8$-cycle.
  4. Compare against $K_{2,n-2}$, which always gives $S=1/4$.

This not only extends the solved range but also isolates a new sharp obstruction: $n=24$ is the first point on the line $m=2n-4$ where the exact value \[ \operatorname{ex}(24;\{C_3,C_4,C_5\})=45 \] exceeds the target edge count $44$, so the present forcing strategy no longer compels a $5$-cycle.

5) WORK (ROUND-5)

As before, for a graph $G$ let \[ \mathcal C(G):=\{\ell\ge 3:\text{$G$ contains a cycle of length $\ell$}\}, \qquad S(G):=\sum_{\ell\in\mathcal C(G)}\frac1\ell. \]

5.1. Exact small-order extremal values

From the exact extremal tables checked in Round 5, we use the following values. Set \[ a_n:=\operatorname{ex}(n;\{C_3,C_4,C_5\}), \qquad b_n:=\operatorname{ex}(n;\{C_3,C_4,C_6\}). \] Then for $14\le n\le 23$ one has \[ \begin{array}{c|cccccccccc} n & 14&15&16&17&18&19&20&21&22&23\\\hline a_n & 21&22&24&26&29&31&34&36&39&42\\ b_n & 18&20&22&24&27&28&30&32&34&36\\ 2n-4 & 24&26&28&30&32&34&36&38&40&42 \end{array} \] In particular, \begin{equation}\label{wsref-0-65-71-3a-73-74-72-69-63-74-31-34-74-6f-32-32} 2n-4>a_n\quad\text{and}\quad 2n-4>b_n\qquad(14\le n\le 22), \end{equation} and at $n=23$ we have \begin{equation}\label{wsref-0-65-71-3a-6e-32-33-65-78-61-63-74} a_{23}=42, \qquad b_{23}=36<42. \end{equation}

5.2. Uniform extension through $n=22$

Proposition (The line $m=2n-4$ for $14\le n\le 22$): Let $14\le n\le 22$, and let $G$ be a graph with $|V(G)|=n$ and $|E(G)|=2n-4$. Then \[ S(G)\ge \frac14. \] Moreover equality is attained by $K_{2,n-2}$.
Proof: By $F1$, $K_{2,n-2}$ has only $4$-cycles, hence $S(K_{2,n-2})=1/4$. So it remains to prove the lower bound for arbitrary $G$.

If $G$ contains $C_3$, then $S(G)\ge 1/3>1/4$. If $G$ contains $C_4$, then $S(G)\ge 1/4$. Thus only the case that $G$ contains neither $C_3$ nor $C_4$ needs attention.

Assume therefore that $G$ has no $C_3$ and no $C_4$. Since $|E(G)|=2n-4>a_n=\operatorname{ex}(n;\{C_3,C_4,C_5\})$ by (eq:strict14to22), $G$ cannot be $C_5$-free; hence $5\in\mathcal C(G)$. Likewise $|E(G)|=2n-4>b_n=\operatorname{ex}(n;\{C_3,C_4,C_6\})$, so $G$ cannot be $C_6$-free; hence $6\in\mathcal C(G)$. Therefore \[ S(G)\ge \frac15+\frac16=\frac{11}{30}>\frac14. \] This proves the lower bound, and $K_{2,n-2}$ gives equality. ∎

5.3. The $n=23$ case

We now settle the first value not covered by Proposition prop:14-22.

Lemma (The unique $(23,42)$ graph with no $C_3,C_4,C_5$ has a $6$-cycle and an $8$-cycle): There is, up to isomorphism, a unique graph $H$ on $23$ vertices and $42$ edges containing no cycle of length $3,4,$ or $5$. The published sparse6 representative is \[ s=\texttt{:V\_\_`abC\_dE`cGfGeHaIbJbKaLeMgNOjKdPQiLcOS\_RS}. \] For this graph one has $6,8\in\mathcal C(H)$.
Proof: Uniqueness is exactly the statement $a_{23}=42$ together with the table entry "ng$=1$" for $n=23$ in the family $\{C_3,C_4,C_5\}$.

It remains to verify that the explicit graph $H$ contains a $6$-cycle and an $8$-cycle. Decoding the sparse6 string gives a graph with edges \[ \{0,1\},\ \{1,8\},\ \{8,10\},\ \{10,12\},\ \{12,2\},\ \{2,0\}, \] so \[ 0-1-8-10-12-2-0 \] is a $6$-cycle, and with edges \[ \{0,1\},\ \{1,8\},\ \{8,10\},\ \{10,12\},\ \{12,18\},\ \{18,19\},\ \{19,22\},\ \{22,0\}, \] we get the $8$-cycle \[ 0-1-8-10-12-18-19-22-0. \] Hence $6,8\in\mathcal C(H)$. ∎

Proposition (The case $(n,m)=(23,42)$): Let $G$ be a graph with $23$ vertices and $42$ edges. Then \[ S(G)\ge \frac14. \] Moreover equality is attained by $K_{2,21}$.
Proof: By $F1$, $S(K_{2,21})=1/4$. So let $G$ be any graph on $23$ vertices with $42$ edges.

If $G$ contains $C_3$, then $S(G)\ge 1/3>1/4$. If $G$ contains $C_4$, then $S(G)\ge 1/4$. So assume that $G$ has no $C_3$ and no $C_4$.

Since $42>b_{23}=\operatorname{ex}(23;\{C_3,C_4,C_6\})=36$ by (eq:n23exact), $G$ must contain a $6$-cycle. If $G$ also contains a $5$-cycle, then \[ S(G)\ge \frac15+\frac16>\frac14, \] and we are done.

It remains only to consider the case that $G$ has no $C_5$. Then $G$ has no $C_3,C_4,C_5$ and has exactly $42=a_{23}$ edges, so by Lemma lem:23-unique $G$ is isomorphic to the unique graph $H$ from that lemma. But $6,8\in\mathcal C(H)$, so \[ S(G)=S(H)\ge \frac16+\frac18=\frac{7}{24}>\frac14. \] Thus every $23$-vertex $42$-edge graph satisfies $S(G)\ge 1/4$, with equality attained by $K_{2,21}$. ∎

5.4. Main Round-5 theorem

Theorem (The $K_{2,n-2}$ line through $n=23$): For every integer $7\le n\le 23$, \[ \min\{S(G): |V(G)|=n,\ |E(G)|=2n-4\}=\frac14. \] The minimum is attained by the complete bipartite graph $K_{2,n-2}$.
Proof: For $7\le n\le 12$ this is exactly $F2$, and for $n=13$ it is exactly $F3$. For $14\le n\le 22$ it is Proposition prop:14-22. For $n=23$ it is Proposition prop:23-42. This exhausts the range $7\le n\le 23$. ∎

6) ADVERSARIAL VERIFICATION

  • Use of Round 4 results. I used Round 4 only as foundation for the already solved cases $7\le n\le 13$ and the formula $S(K_{2,n-2})=1/4$. No Round 4 proof was reproved.

  • Dependence on external tables. The argument for $14\le n\le 23$ uses only exact table entries (not asymptotics): the ANU page explicitly states that when neither "ne" nor "ng" is preceded by $\ge$, the Turán number and all extremal graphs are exact. That hypothesis holds for every table entry used here.

  • Strict inequalities for $14\le n\le 22$. These were checked entry-by-entry in (eq:strict14to22). There is no hidden asymptotic step.

  • The $n=23$ boundary case. Here the $C_5$-forcing inequality fails exactly, since $a_{23}=42=2\cdot 23-4$. The proof therefore isolates the no-$C_5$ case and handles it separately via the unique extremal graph $H$. This is the only place where the argument uses an explicit graph.

  • Computational content in Lemma lem:23-unique. The computational step is exact and finite: one decodes a published sparse6 graph and reads off the listed edges, which visibly contain one $6$-cycle and one $8$-cycle. No random search or heuristic is used.

  • Why equality cannot occur away from $K_{2,n-2}$. Every non-$K_{2,n-2}$ case handled in the proof actually gives a strict inequality $S(G)>1/4$ (either from a triangle, from $C_5$ and $C_6$, or from $C_6$ and $C_8$ in the exceptional $n=23$ graph).

7) FINAL (EXACTLY ONE)

UNRESOLVED (BUT STRICTLY ADVANCED).

Round 5 proves a substantially stronger theorem than Round 4: for every $7\le n\le 23$, among all graphs with $n$ vertices and $2n-4$ edges, \[ \min S(G)=\frac14, \] and the complete bipartite graph $K_{2,n-2}$ is a minimiser. Thus the entire $a=2$ complete-bipartite line is now settled up to $n=23$. The first unresolved value on this line is $n=24$. The full Erdős--Hajnal minimiser question for arbitrary $(n,m)$ remains open.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 90%

9) REFERENCES

References

  • [AfzalyMcKayData] N. Afzaly and B. D. McKay, Extremal Graphs and Turan numbers (combinatorial data page), Australian National University. Used here for the exact tables for $\operatorname{ex}(n;\{C_3,C_4,C_5\})$ and $\operatorname{ex}(n;\{C_3,C_4,C_6\})$.
  • [McKay23Graph] B. D. McKay, Sparse6 file for the unique graph on $23$ vertices and $42$ edges with no $C_3,C_4,C_5$, file c345_n23e42.s6 on the ANU extremal-graph data page. Used here only for the exact finite verification in Lemma lem:23-unique.