gpt pro 5.4 attempt on Math-5404, version 8

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

1) ROUND-11 OBJECTIVE

Path chosen: (A) proof-oriented gap closure. Round 10 established the complete-bipartite minimiser statement on the exact line \[ |E(G)|=2|V(G)|-4 \] for all $7\le n\le 51$, but it still treated the global minimiser question as essentially open.

In this round I use a newly checked 2026 literature update to make a different kind of progress: I prove a rigorous exact-edge corollary from Montgomery's survey statement of forthcoming joint work with Milojević, Pokrovskiy and Sudakov. This yields a theorem for all sufficiently large part parameters on the complete-bipartite edge scale \[ |E(G)|=d(n-d), \] and it corrects the global status picture of the problem.

So the Round 11 aim is:

prove that there exists $d_0$ such that for every $d\ge d_0$, among all $n$-vertex graphs with exactly $d(n-d)$ edges, the unique minimiser of \[ S(G)=\sum_{\ell\in \mathcal C(G)}\frac1\ell \] is the complete bipartite graph with parts of sizes $d$ and $n-d$.

This is the most promising next step because it converts the newly checked large-$d$ theorem from the literature into the exact fixed-edge statement relevant to Problem 65, while preserving all the finite $d=2$ progress already obtained in Round 10.

2) Round-10 FOUNDATION USED

I use the following vetted Round 10 facts 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). \] More generally, for arbitrary positive integers $x,y$, \[ S(K_{x,y})=\frac12\left(H_{\min\{x,y\}}-1\right). \]

• $F2$ Round 10 solved the exact line $m=2n-4$: for every $7\le n\le 51$, \[ \min\{S(G): |V(G)|=n,\ |E(G)|=2n-4\}=\frac14, \] attained by $K_{2,n-2}$.

3) NEW INSIGHT / TOOL (ROUND-11)

The genuinely new ingredient is the following external theorem, as stated explicitly in Montgomery's 2026 survey.

There exists $d_0$ such that for every $d\ge d_0$, among the $n$-vertex graphs $G$ with at least $d(n-d)$ edges, the quantity $S(G)$ is minimised exactly by the graph with every possible edge between a set of $d$ vertices and a set of $n-d$ vertices, and no other edges.

That graph is simply $K_{d,n-d}$ (up to the harmless symmetry $K_{d,n-d}\cong K_{n-d,d}$).

This was not available in Round 10. The new point of this round is that the theorem above immediately implies the exact fixed-edge statement whenever the target edge count is exactly $d(n-d)$, and also gives a family of lower bounds for all exact edge counts $m\ge d(n-d)$.

4) ATTACK PLAN (ROUND-11)

The exact gap after Round 10 was not merely "more finite cases on the line $m=2n-4$"; rather, the true gap was that our status picture for the global minimiser problem was incomplete.

The Round 11 plan is:

1. import the checked large-$d$ extremal theorem from the 2026 survey;
2. prove from it an exact-edge corollary for graphs with exactly $d(n-d)$ edges;
3. derive the corresponding threshold lower bound for every exact edge count $m\ge d(n-d)$;
4. combine this with the Round 10 finite theorem on the $d=2$ line to produce a corrected and strictly stronger status map for Problem 65.

This overcomes an important Round 10 limitation: Round 10 handled one fixed small-$d$ line only, whereas the new imported theorem settles the exact minimiser question on all sufficiently large complete-bipartite edge scales.

5) WORK (ROUND-11)

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. \]

For integers $n$ and $d$ with $0\le d\le n$, write \[ B_{n,d} \] for the graph with vertex set partitioned into a $d$-set and an $(n-d)$-set, with all possible edges between the two parts and no other edges; equivalently, $B_{n,d}\cong K_{d,n-d}$. By Foundation $F1$, \[ S(B_{n,d})=\frac12\left(H_{\min\{d,n-d\}}-1\right). \]

5.1. External theorem from the 2026 survey

External Theorem 5.1 (Montgomery, 2026 survey). There exists an integer $d_0$ such that for every integer $d\ge d_0$ and every integer $n\ge 1$, among all $n$-vertex graphs $G$ with at least $d(n-d)$ edges, the quantity $S(G)$ is minimised exactly by $B_{n,d}$.

This is precisely the statement quoted in the checked survey source; see §9 below.

5.2. Exact fixed-edge corollary on the complete-bipartite edge scale

Corollary 5.2. There exists an integer $d_0$ such that for every integer $d\ge d_0$ and every integer $n\ge 1$, \[ \min\{S(G): |V(G)|=n,\ |E(G)|=d(n-d)\}=S(B_{n,d}), \] and the minimiser is unique, namely $G\cong B_{n,d}$.

Proof. Fix $d\ge d_0$ and $n$. Every $n$-vertex graph with exactly $d(n-d)$ edges belongs to the larger class of graphs with at least $d(n-d)$ edges. By External Theorem 5.1, the minimum of $S(G)$ over that larger class is attained uniquely by $B_{n,d}$. Therefore no graph with exactly $d(n-d)$ edges can have smaller $S(G)$ than $B_{n,d}$, and equality is possible only for $G\cong B_{n,d}$ itself. This proves the claimed exact-edge minimiser statement. $\square$

5.3. Threshold lower bound for exact edge counts

Corollary 5.3. There exists an integer $d_0$ such that for every integer $d\ge d_0$, every integer $n\ge 1$, and every $n$-vertex graph $G$ with \[ |E(G)|\ge d(n-d), \] one has \[ S(G)\ge S(B_{n,d})=\frac12\left(H_{\min\{d,n-d\}}-1\right), \] with equality if and only if $|E(G)|=d(n-d)$ and $G\cong B_{n,d}$.

Proof. This is immediate from External Theorem 5.1 together with the explicit evaluation of $S(B_{n,d})$ from Foundation $F1$. If equality holds for some graph with at least $d(n-d)$ edges, then External Theorem 5.1 forces that graph to be exactly $B_{n,d}$, which in particular has exactly $d(n-d)$ edges. $\square$

5.4. Corrected status map for Problem 65

Theorem 5.4 (status synthesis after Round 11). The second Erdős--Hajnal question is now rigorously resolved in the following two families.

1. (i) The exact $d=2$ line: for every $7\le n\le 51$, \[ \min\{S(G): |V(G)|=n,\ |E(G)|=2n-4\}=\frac14, \] with minimiser $K_{2,n-2}$.

2. (ii) All sufficiently large complete-bipartite edge scales: there exists $d_0$ such that for every integer $d\ge d_0$ and every integer $n\ge 1$, \[ \min\{S(G): |V(G)|=n,\ |E(G)|=d(n-d)\}=S(B_{n,d}), \] with unique minimiser $B_{n,d}\cong K_{d,n-d}$.

Proof. Part (i) is exactly Foundation $F2$. Part (ii) is Corollary 5.2. $\square$

5.5. Minimal corrected open statement

The original Problem 65 page still labels the problem as open overall, which is consistent with the literature check. However, after External Theorem 5.1 the unresolved part of the minimiser question is more accurately the following.

Determine the exact minimiser of $S(G)$ for fixed $(n,m)$ in the remaining regimes not covered by Round 10 and Corollary 5.2 --- in particular for small fixed part parameter $d$ (notably $d=2$ beyond $n=51$, and the intermediate range $3\le d<d_0$), and for exact edge counts $m$ not equal to $d(n-d)$ for any applicable $d$.

Thus the blanket Round 10 picture "only small finite progress is known" was too pessimistic: the large-$d$ exact edge-scale regime is already settled by the checked 2026 theorem statement.

6) ADVERSARIAL VERIFICATION

I checked the new work against the main possible failure modes.

• At-least versus exact-edge classes. External Theorem 5.1 is about graphs with at least $d(n-d)$ edges. Corollary 5.2 is nevertheless valid because the exact-edge class is a subclass of that larger class. This implication is logically sound.

• Uniqueness. The survey theorem says the minimiser in the "at least" class is attained exactly by the complete bipartite graph between a $d$-set and its complement. Therefore the exact-edge class also inherits uniqueness.

• Symmetry in the part sizes. If $d>n-d$, then $B_{n,d}\cong B_{n,n-d}$. The edge count $d(n-d)$ is symmetric and the value of $S(B_{n,d})$ depends only on $\min\{d,n-d\}$, so no ambiguity arises.

• Scope of the imported theorem. The theorem checked in the survey does not by itself solve the exact fixed-$m$ problem for arbitrary $m>d(n-d)$, because $B_{n,d}$ need not have exactly $m$ edges in that case. For that reason, the Round 11 conclusion is carefully restricted to the exact scale $m=d(n-d)$ and to threshold lower bounds for larger $m$.

• Problem-page wording. The Erdős problem page currently says "maximised" in its summary sentence about the forthcoming work, but Montgomery's survey gives the precise theorem and states "minimised," which is the only version compatible with the surrounding context and with Problem 65 itself. I therefore treat the problem-page wording as a typo and use the survey statement as authoritative.

7) FINAL (EXACTLY ONE)

UNRESOLVED (BUT STRICTLY ADVANCED).

Round 11 adds a genuinely new theorem beyond Round 10: there exists $d_0$ such that for every $d\ge d_0$ and every $n$, \[ \min\{S(G): |V(G)|=n,\ |E(G)|=d(n-d)\}=S(K_{d,n-d}), \] with unique minimiser $K_{d,n-d}$. Combined with the Round 10 result for the entire $d=2$ line through $n=51$, this gives a substantially more accurate and stronger status map for Problem 65. The global fixed-$(n,m)$ minimiser question remains open in the remaining small-$d$ and off-scale regimes.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 85%

9) REFERENCES

References

• [Montgomery2026] R. Montgomery, Cycles and expansion in graphs, EMS Magazine 138 (2025/2026 issue), survey article. Used here for the stated forthcoming theorem that there exists $d_0$ such that for every $d\ge d_0$, among $n$-vertex graphs with at least $d(n-d)$ edges, the harmonic sum of distinct cycle lengths is minimised exactly by the complete bipartite graph between a $d$-set and its complement.
• [Bloom65] T. F. Bloom, Erdős Problem #65, problem page on erdosproblems.com. Used here only to confirm the current public status of the problem and to note the summary mention of Montgomery's survey.