we-solve (beta)

Math-5404-A5 · revision r1 · on Math-5404

gpt pro 5.2 attempt on Math-5404, version 3

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. Erdős--Hajnal reciprocal cycle-length sum (Round 3)
  2. 1) ROUND-3 OBJECTIVE
  3. 2) ROUND-2 FOUNDATION USED
  4. 3) NEW INSIGHT / TOOL (ROUND 3)
  5. 4) ATTACK PLAN (ROUND 3)
  6. 5) WORK (ROUND 3)
  7. 5.1. Notation
  8. 5.2. A $2$-path bound for $(C_3,C_4)$-free graphs
  9. 5.3. New exact minimisers for the $K_{2,n-2}$ line
  10. 6) ADVERSARIAL VERIFICATION
  11. 7) FINAL (EXACTLY ONE)
  12. 8) COMPLETION ESTIMATE (MANDATORY)
  13. 9) REFERENCES

Erdős--Hajnal reciprocal cycle-length sum (Round 3)

1) ROUND-3 OBJECTIVE

Path chosen: (A) proof-oriented gap closure. Round 2 left the global minimiser question open but produced (i) exact minimisers for several small parameter pairs and (ii) a structural mechanism ruling out dense balanced bipartite competitors.

In this round we add a new uniform method for the complete-bipartite family $K_{2,n-2}$: we prove an extremal bound for graphs with no $3$- or $4$-cycles and use it to settle several new exact parameter pairs.

2) ROUND-2 FOUNDATION USED

We rely on the following Round 2 results without re-proving them.

  • (R2 Lemma 1) For $2\le a\le b$, the complete bipartite graph $K_{a,b}$ has distinct cycle lengths \[\{4,6,8,\dots,2a\}\qquad\text{and hence}\qquad S(K_{a,b})=\sum_{j=2}^a\frac1{2j}=\tfrac12(H_a-1).\]
  • (R2 Proposition 8--12) For $(n,m)=(8,12)$, every $8$-vertex $12$-edge graph $G$ satisfies $S(G)\ge 1/4$, with equality achieved by $K_{2,6}$.
  • (R2 Theorem ES) (External tool used in Round 2.) Dense balanced bipartite graphs are bipancyclic above the Entringer--Schmeichel threshold, yielding a lower bound on $S(G)$ for that competitor class.

3) NEW INSIGHT / TOOL (ROUND 3)

The new tool is a sharp $2$-path counting inequality for graphs with girth at least $5$:

If $G$ has no $C_3$ and no $C_4$, then its number of edges satisfies \[|E(G)|\le \frac{n\sqrt{n-1}}{2}.\]

This immediately forces the presence of a triangle or a $4$-cycle whenever $m>\frac{n\sqrt{n-1}}{2}$. For the parameter line $m=2n-4$ (which corresponds to $K_{2,n-2}$), this yields new exact minimisation results for all $n\le 12$, extending Round 2's solved case $(8,12)$ (and subsuming its ad hoc proof).

4) ATTACK PLAN (ROUND 3)

Round 2 proved exact minimisation for $(n,m)=(8,12)$ but had no general method. The remaining gap for this family is:

For which $n$ does every $n$-vertex graph with $m=2n-4$ edges necessarily contain a triangle or a $4$-cycle?

If this is forced, then automatically $S(G)\ge 1/4$ (since $1/3>1/4$), and the complete bipartite graph $K_{2,n-2}$ achieves equality because it has only $4$-cycles.

We prove a general extremal bound for $(C_3,C_4)$-free graphs and compare it to $2n-4$.

5) WORK (ROUND 3)

5.1. Notation

For a graph $G$, let \[\mathcal C(G):=\{\ell\ge 3:\ G\text{ contains a (simple) cycle of length }\ell\},\qquad S(G):=\sum_{\ell\in\mathcal C(G)}\frac1\ell.\] The sum is over distinct cycle lengths.

5.2. A $2$-path bound for $(C_3,C_4)$-free graphs

Lemma (Counting $2$-paths): Let $G$ be a graph on $n$ vertices with $m$ edges. If $G$ is triangle-free and $C_4$-free, then \begin{equation}\label{wsref-0-65-71-3a-32-70-61-74-68-2d-69-6e-65-71} \sum_{v\in V(G)}\binom{d(v)}{2}\ \le\ \binom{n}{2}-m. \end{equation}
Proof: A (directed) $2$-path is an ordered triple $(x,v,y)$ with distinct vertices and edges $xv,vy\in E(G)$. For each middle vertex $v$, there are $\binom{d(v)}{2}$ unordered endpoint pairs $\{x,y\}$ giving such a $2$-path, so the total number of (unordered-endpoint) $2$-paths is $\sum_v \binom{d(v)}{2}$.

Because $G$ is triangle-free, the endpoints $x,y$ of any $2$-path $x-v-y$ are nonadjacent. Thus each $2$-path determines a non-edge $\{x,y\}\notin E(G)$.

Because $G$ is $C_4$-free, no unordered pair $\{x,y\}$ can be the endpoints of two distinct $2$-paths: if $x-v-y$ and $x-v'-y$ were distinct $2$-paths with the same endpoints, then $x-v-y-v'-x$ would be a $4$-cycle.

Hence the map "$2$-path $\mapsto$ its endpoint pair" injects into the set of non-edges, which has size $\binom{n}{2}-m$. This proves (eq:2path-ineq). ∎

Lemma (Edge upper bound for girth $\ge 5$): Let $G$ be a graph on $n$ vertices with $m$ edges. If $G$ has no $C_3$ and no $C_4$, then \[m\le \frac{n\sqrt{n-1}}{2}. \] In particular, if $m>\frac{n\sqrt{n-1}}{2}$ then $G$ contains a triangle or a $4$-cycle.
Proof: Start from Lemma lem:2paths. Using $\binom{d}{2}=\frac12(d^2-d)$ and $\sum_v d(v)=2m$, we have \[ \sum_v\binom{d(v)}{2}=\frac12\sum_v d(v)^2-m. \] By Cauchy--Schwarz, \[\sum_v d(v)^2\ \ge\ \frac1n\left(\sum_v d(v)\right)^2\ =\ \frac{(2m)^2}{n}. \] Therefore \[ \sum_v\binom{d(v)}{2}\ \ge\ \frac12\cdot\frac{4m^2}{n}-m\ =\ \frac{2m^2}{n}-m. \] Combine with Lemma lem:2paths: \[ \frac{2m^2}{n}-m\ \le\ \binom{n}{2}-m. \] Cancel $-m$ and rearrange: \[ \frac{2m^2}{n}\ \le\ \frac{n(n-1)}{2} \qquad\Longrightarrow\qquad m^2\ \le\ \frac{n^2(n-1)}{4} \qquad\Longrightarrow\qquad m\ \le\ \frac{n\sqrt{n-1}}{2}. \] The final "in particular" follows by contrapositive. ∎

5.3. New exact minimisers for the $K_{2,n-2}$ line

Proposition (Exact minimisation for $(n,m)=(n,2n-4)$ up to $n=12$): Let $7\le n\le 12$ and let $G$ be a graph on $n$ vertices with $m=2n-4$ edges. Then \[S(G)\ge \frac14. \] Moreover $S(K_{2,n-2})=1/4$, so $\min S(G)=1/4$ for these parameter pairs, and a complete bipartite graph is a minimiser.
Proof: First, by (R2 Lemma 1) the complete bipartite graph $K_{2,n-2}$ has only $4$-cycles, hence $S(K_{2,n-2})=1/4$.

Now let $G$ be any $n$-vertex graph with $m=2n-4$ edges. If $G$ contains a triangle $C_3$, then $S(G)\ge 1/3>1/4$. So we may assume $G$ is triangle-free.

If $G$ contains a $4$-cycle, then $S(G)\ge 1/4$ and we are done. Thus the only way to have $S(G)<1/4$ would be for $G$ to contain no $C_3$ and no $C_4$.

But for $7\le n\le 12$ we have the strict inequalities \[ 2n-4\ >\ \frac{n\sqrt{n-1}}{2} \qquad\text{(checked below),} \] so Lemma lem:edges-girth5 forbids the existence of a $(C_3,C_4)$-free graph with $m=2n-4$. Therefore every such $G$ has a $C_3$ or $C_4$, and in either case $S(G)\ge 1/4$.

For completeness, the numerical comparisons are: \[ \begin{array}{c|c|c} n & 2n-4 & \tfrac{n\sqrt{n-1}}{2}\\\hline 7 & 10 & \approx 8.57\\ 8 & 12 & \approx 10.58\\ 9 & 14 & \approx 12.73\\ 10 & 16 & 15\\ 11 & 18 & \approx 17.39\\ 12 & 20 & \approx 19.90 \end{array} \] This finishes the proof. ∎

Remark (Where the method breaks): For $n=13$ one has $2n-4=22<\tfrac{13\sqrt{12}}{2}\approx 22.52$, so Lemma lem:edges-girth5 no longer forces a $C_3$ or $C_4$ on the line $m=2n-4$. Thus if the complete-bipartite minimiser conjecture were to fail first for the family $K_{2,n-2}$, $n=13$ is the first place this counting argument leaves room.

6) ADVERSARIAL VERIFICATION

  • Does Lemma lem:2paths overcount $2$-paths? We count unordered endpoint pairs at each middle vertex $v$, giving exactly $\binom{d(v)}{2}$. Different middle vertices produce distinct $2$-paths. This is the standard counting identity.

  • Is "two $2$-paths with the same endpoints give a $C_4$" always valid? Yes: if $x-v-y$ and $x-v'-y$ with $v\neq v'$, then the edges $xv,vy,yv',v'x$ form a $4$-cycle on $\{x,v,y,v'\}$. No further edges are needed.

  • Triangle-free necessity in Lemma lem:2paths. If $xy$ were an edge, a $2$-path $x-v-y$ would create a triangle. Thus in a triangle-free graph, endpoints of any $2$-path are automatically nonadjacent, which is exactly what allows the injection into non-edges.

  • Sharpness / boundary issues. Lemma lem:edges-girth5 is tight up to rounding for certain $n$ (it is the usual "Reiman-type" bound). For the present application we only need strict separation $2n-4>\tfrac{n\sqrt{n-1}}{2}$, which holds for $n\le 12$ and fails at $n=13$, consistent with the numerical table.

  • Cycle lengths in $K_{2,n-2}$. Any simple cycle in a bipartite graph alternates between parts. With a part of size $2$, a simple cycle can use at most $2$ vertices from that part, hence must have length exactly $4$. So $\mathcal C(K_{2,n-2})=\{4\}$ and $S(K_{2,n-2})=1/4$.

7) FINAL (EXACTLY ONE)

UNRESOLVED (BUT STRICTLY ADVANCED).

Round 3 adds a new extremal lemma for $(C_3,C_4)$-free graphs and uses it to prove an explicit new block of exact minimiser instances: for every $7\le n\le 12$ with $m=2n-4$, one has $\min S(G)=1/4$, achieved by $K_{2,n-2}$. This both extends and conceptually simplifies the Round 2 solved case $(8,12)$. The global "complete bipartite minimises $S$" question remains open.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 55%

9) REFERENCES

  1. A. Gyárfás, J. Komlós, and E. Szemerédi, On the distribution of cycle lengths in graphs, J. Graph Theory 8 $1984$, 441--462.

  2. H. Liu and R. Montgomery, A solution to Erdős and Hajnal's odd cycle problem, J. Amer. Math. Soc. 36 $2023$, 1191--1234.

  3. R. C. Entringer and E. F. Schmeichel, Edge conditions and cycle structure in bipartite graphs, Ars Combinatoria 26 $1988$, 229--232.