An extremal theorem for positive curvature of graphs

Kaizhe Chen; Shiping Liu; Zhe You

arxiv: 2607.02297 · v1 · pith:K4N66OABnew · submitted 2026-07-02 · 🧮 math.CO · math.DG

An extremal theorem for positive curvature of graphs

Kaizhe Chen , Shiping Liu , Zhe You This is my paper

Pith reviewed 2026-07-03 10:24 UTC · model grok-4.3

classification 🧮 math.CO math.DG

keywords extremal graphsOllivier curvatureLin-Lu-Yau curvaturepositive curvaturediscrete curvaturegraph theoryedge thresholds

0 comments

The pith

Every graph on n≥8 vertices exceeding T(n) edges has positive Ollivier/Lin-Lu-Yau curvature.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves a sharp extremal result linking the number of edges in a graph to the sign of its Ollivier/Lin-Lu-Yau curvature. Specifically, any graph with n at least 8 vertices and more than T(n) = (n squared minus 3n over 2) minus ceiling of n over 2 plus 2 edges must have positive curvature on all its edges. The authors demonstrate that this edge threshold is optimal by exhibiting graphs with exactly T(n) edges that include at least one edge of non-positive curvature. For even n at least 12, such an extremal graph is unique, while for smaller even n and odd n the examples are not unique. This work points toward a broader program of extremal questions defined by discrete curvature conditions rather than classical forbidden subgraphs.

Core claim

We prove an extremal theorem for positive Ollivier/Lin--Lu--Yau curvature: every graph of order n≥8 with more than T(n)=(n²-3n)/2 - ceil(n/2) +2 edges has positive Ollivier/Lin--Lu--Yau curvature, and this threshold is optimal. Moreover, for even n≥12, there exists a unique graph with T(n) edges that has an edge with non-positive curvature. For n=8,10 and odd n≥9, the extremal graphs are not unique.

What carries the argument

The extremal edge count T(n) that separates graphs guaranteed to have all positive Ollivier/Lin-Lu-Yau curvature edges from those permitted to contain a non-positive curvature edge.

If this is right

Any graph with more than T(n) edges has positive curvature on every edge.
The bound T(n) is achieved by graphs containing at least one non-positive curvature edge.
For even n at least 12 the graph achieving T(n) edges while having a non-positive curvature edge is unique.
Multiple distinct graphs achieve T(n) edges with a non-positive curvature edge when n equals 8 or 10 or is odd and at least 9.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The suggestion of a new class of curvature-defined extremal problems implies that analogous sharp thresholds may exist when Ollivier curvature is replaced by other discrete curvature notions.
The explicit form of T(n) may allow rephrasing the curvature condition as the avoidance of certain local edge configurations, potentially linking the result to classical extremal graph theory.

Load-bearing premise

Optimality requires that there exist graphs with exactly T(n) edges containing at least one edge of non-positive curvature whose curvature values have been correctly computed.

What would settle it

A single graph on n vertices with more than T(n) edges that still contains an edge of non-positive Ollivier/Lin-Lu-Yau curvature would disprove the theorem.

Figures

Figures reproduced from arXiv: 2607.02297 by Kaizhe Chen, Shiping Liu, Zhe You.

**Figure 1.** Figure 1: A schematic of the graph G. Consider the function f : N(x) ∪ N(y) → Z given by f(z) =    −1, if z ∈ A; 0, if z ∈ {x} ∪ B; 1, if z ∈ {y, w}. Then, f(y) − f(x) = 1 and f ∈ Lip(1). By Theorem 2.3, we have κLLY (x, y) ≤ ∆f(x) − ∆f(y) = 1 n − 2 1 − ln 2 m − 1 2 (1 + 0 − 2) ≤ 0. This completes the proof. 14 [PITH_FULL_IMAGE:figures/full_fig_p014_1.png] view at source ↗

**Figure 2.** Figure 2: A schematic of the graph G1. We next estimate the Lin–Lu–Yau curvature κLLY (x, y) of xy. Consider the function f1 : N(x) ∪ N(y) → Z given by f1(z) =    −1, if z ∈ A; 0, if z ∈ {x} ∪ B; 1, if z ∈ {y, w}. Then, f1(y) − f1(x) = 1 and f1 ∈ Lip(1). By Theorem 2.3, we have κLLY (x, y) ≤ 1 n − 3 1 − n − 1 2 − 1 2 (1 + 0 − 2) = 0. 15 [PITH_FULL_IMAGE:figures/full_fig_p015_2.png] view at source ↗

**Figure 3.** Figure 3: A schematic of the graph G2. consider the function f2 : N(x) ∪ N(y) → Z given by f2(z) =    −1, if z ∈ A; 0, if z ∈ {x} ∪ B; 1, if z ∈ {y, w}. Then, Theorem 2.3 yields κLLY (x, y) ≤ 1 n − 1 2 − n + 3 2 − 1 2 (1 + 0 − 2) = 0. Finally, we present an example for 7 ≤ n ≤ 11 to illustrate that the conditions n ≥ 8 and n ≥ 12 in Theorem 1.1 are both necessary. Let H = (V, E) be the graph of order n defi… view at source ↗

**Figure 4.** Figure 4: A schematic of the graph H. For n = 8, 9, 10, 11, select a = n 2 and b = n 2 −2. Then H has exactly n 2−3n 2 − n 2 +2 edges. It is direct to check that H has some edges with non-positive Lin–Lu–Yau curvature by using the graph curvature calculator [8], which is a freely accessible interactive app at https://www.mas.ncl.ac.uk/graph-curvature/. This illustrates that the condition n ≥ 12 in Theore… view at source ↗

**Figure 5.** Figure 5: A graph of order 7 containing edges of negative LLY curvature. [PITH_FULL_IMAGE:figures/full_fig_p017_5.png] view at source ↗

read the original abstract

We prove an extremal theorem for positive Ollivier/Lin--Lu--Yau curvature: every graph of order $n\geq 8$ with more than \[ T(n)=\frac{n^2-3n}{2}-\left\lceil\frac{n}{2}\right\rceil+2 \] edges has positive Ollivier/Lin--Lu--Yau curvature, and this threshold is optimal. Moreover, for even $n\geq 12$, there exists a unique graph with $T(n)$ edges that has an edge with non-positive curvature. For $n=8,10$ and odd $n\geq 9$, the extremal graphs are not unique. This suggests a new class of extremal graph-theoretic problems arising from discrete curvature notions.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper pins down an explicit sharp threshold T(n) for graphs to have all edges with positive Ollivier/Lin-Lu-Yau curvature, plus uniqueness for even n≥12, but optimality hinges on the curvature signs of the T(n)-edge constructions.

read the letter

The main takeaway is that any graph on n≥8 vertices with more than T(n)=(n²-3n)/2 - ceil(n/2)+2 edges has positive Ollivier/Lin-Lu-Yau curvature on every edge, and the bound is tight. For even n≥12 the extremal graph is claimed to be unique; for n=8,10 and odd n the examples are not unique.

What is new is the closed-form T(n) together with the uniqueness classification by parity. The paper sets up the extremal question cleanly and supplies both the forcing direction (more edges implies all curvatures positive) and matching constructions at the threshold.

The work is direct about the discrete curvature definition and states the result for n starting at 8. That gives a usable, concrete bound rather than an asymptotic one.

The soft spot is the optimality step. The upper bound can stand on its own, but sharpness requires that the specific T(n)-edge graphs really contain at least one edge with curvature ≤0. The stress-test note correctly flags this calculation as the least secure link; without machine-checked verification or an independent enumeration for the small cases, a referee would need to check those sign computations carefully. The non-uniqueness statements for smaller and odd n are fine as stated, but they still rest on the same curvature evaluations.

This is a narrow but precise result for people working on discrete geometry and curvature notions on graphs. A reader already following Ollivier or Lin-Lu-Yau curvature in combinatorial settings would get immediate use from the explicit threshold and the uniqueness claims. The paper shows clear engagement with the literature and a self-contained claim, so it deserves a serious referee even if the boundary constructions need extra scrutiny.

Referee Report

1 major / 0 minor

Summary. The manuscript proves that every graph on n≥8 vertices with more than T(n)=(n²-3n)/2 - ⌈n/2⌉ +2 edges has positive Ollivier/Lin-Lu-Yau curvature on every edge, and that the threshold T(n) is optimal because there exist graphs with exactly T(n) edges containing at least one edge of non-positive curvature. For even n≥12 the extremal graph is claimed to be unique; for n=8,10 and odd n≥9 the extremal graphs are not unique.

Significance. If correct, the result supplies the first sharp extremal threshold for the property that all edges have positive Ollivier/Lin-Lu-Yau curvature. It therefore initiates a new family of curvature-driven extremal problems in graph theory and supplies concrete, computable bounds that can be tested against known curvature formulas.

major comments (1)

The optimality statement (that T(n) is sharp) rests on explicit constructions of graphs with exactly T(n) edges together with a verification that at least one edge has non-positive curvature. Because this verification is load-bearing for the sharpness claim and no machine-checked enumeration or independent curvature computation is supplied, the manuscript must include a self-contained calculation of the curvature values on the claimed extremal graphs (particularly the unique graph asserted for even n≥12).

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and the constructive comment on strengthening the optimality claim. We respond point-by-point below.

read point-by-point responses

Referee: The optimality statement (that T(n) is sharp) rests on explicit constructions of graphs with exactly T(n) edges together with a verification that at least one edge has non-positive curvature. Because this verification is load-bearing for the sharpness claim and no machine-checked enumeration or independent curvature computation is supplied, the manuscript must include a self-contained calculation of the curvature values on the claimed extremal graphs (particularly the unique graph asserted for even n≥12).

Authors: We agree that the sharpness of T(n) requires explicit, self-contained verification of non-positive curvature on at least one edge of each extremal construction. In the revised manuscript we will add a dedicated subsection containing the full curvature computations (using the standard Ollivier/Lin-Lu-Yau formula) for the unique extremal graph when n is even and ≥12, as well as for the representative constructions in the remaining cases. These calculations will be presented step-by-step so that they can be checked directly from the text. revision: yes

Circularity Check

0 steps flagged

No significant circularity; direct proof with explicit extremal examples

full rationale

The derivation consists of a direct proof that graphs exceeding the explicit combinatorial threshold T(n) must have positive Ollivier/Lin-Lu-Yau curvature on all edges, together with separate verification of optimality by constructing specific graphs attaining T(n) edges and computing their curvature signs. No step reduces a claimed prediction to a fitted input by construction, no self-citation is invoked as a load-bearing uniqueness theorem, and the formula for T(n) is stated independently of the curvature sign. The explicit construction for optimality is a standard non-circular verification step rather than a re-derivation.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the standard definition of Ollivier/Lin-Lu-Yau curvature from prior literature and basic axioms of finite undirected graphs; no new free parameters or invented entities are introduced in the abstract.

axioms (1)

domain assumption Ollivier/Lin-Lu-Yau curvature is defined on graphs via the standard formula involving Wasserstein distance between neighbor measures.
The paper applies this established definition without re-deriving it.

pith-pipeline@v0.9.1-grok · 5654 in / 1169 out tokens · 31953 ms · 2026-07-03T10:24:09.435236+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

18 extracted references · 2 canonical work pages · 2 internal anchors

[1]

Ollivier Ricci curvature on graphs obtained by removing edges from complete graphs

Y. Asai and T. Yamada, Ollivier Ricci curvature on graphs obtained by removing edges from complete graphs, arXiv preprint arXiv:2605.30830 (2026)

work page internal anchor Pith review Pith/arXiv arXiv 2026
[2]

Bakry and M

D. Bakry and M. Émery, Diffusions hypercontractives, Séminaire de probabilités, XIX, 1983/84, 177–206, Lecture Notes in Math. 1123, Springer, Berlin, 1985

1983
[3]

Bollobás,Extremal graph theory, reprint of the 1978 original, Dover, Mineola, NY, 2004

B. Bollobás,Extremal graph theory, reprint of the 1978 original, Dover, Mineola, NY, 2004

1978
[4]

D. P. Bourne, D. Cushing, S. Liu, F. Münch and N. Peyerimhoff, Ollivier-Ricci idleness functions of graphs, SIAM J. Discrete Math. 32(2) (2018) 1408-1424

2018
[5]

K. Chen, S. Liu, Z. You, Connectivity versus Lin–Lu–Yau curvature, Int. Math. Res. Not., 19 (2025), rnaf303

2025
[6]

K. Chen, S. Liu, Z. You, Criteria on forbidden subgraphs in the complements for positive Lin–Lu–Yau curvature, arXiv preprint arXiv: 2605.03470 (2026)

work page internal anchor Pith review Pith/arXiv arXiv 2026
[7]

Cushing, S

D. Cushing, S. Kamtue, J. H. Koolen, S. Liu, F. Münch, N. Peyerimhoff, Rigidity of the Bonnet-Myers inequality for graphs with respect to Ollivier Ricci curvature, Adv. Math. 369 (2020), 107188

2020
[8]

Cushing, R

D. Cushing, R. Kangaslampi, V. Lipiäinen, S. Liu and G. W. Stagg, The graph cur- vature calculator and the curvatures of cubic graphs, Exp. Math. 31 (2022), no. 2, 583-595

2022
[9]

K.Devriendt, R.Lambiotte, Discretecurvatureongraphsfromtheeffectiveresistance, J. Phys. Complex. 3 (2) (2022) 025008

2022
[10]

Füredi and M

Z. Füredi and M. Simonovits, The history of degenerate (bipartite) extremal graph problems, inErdös centennial, 169–264, Bolyai Soc. Math. Stud., 25, János Bolyai Math. Soc., Budapest
[11]

1, Paper No

M.Hehl, RegulargraphswithpositiveOllivier-Riccicurvature, Math.Ann.394(2026), no. 1, Paper No. 24, 28 pp

2026
[12]

Y. Li, W. J. Liu and L. H. Feng, A survey on spectral conditions for some extremal graph problems, Adv. Math. (China)51(2022), no. 2, 193–258

2022
[13]

Y. Lin, L. Lu and S.-T. Yau, Ricci curvature of graphs, Tohoku Math. J. 63 (2011), no. 4, 605-627

2011
[14]

Lin and S.-T

Y. Lin and S.-T. Yau, Ricci curvature and eigenvalue estimate on locally finite graphs, Math. Res. Lett. 17 (2010), no. 2, 343-356. 18

2010
[15]

Münch and R

F. Münch and R. Wojciechowski, Ollivier Ricci curvature for general graph Laplacians: heatequation, Laplaciancomparison, non-explosionanddiameterbounds, Adv.Math. 356 (2019), 106759, 45 pp

2019
[16]

Najman and P

L. Najman and P. Romon (Eds), Modern approaches to discrete curvature, Lecture Notes in Math., 2184, Springer, Cham, 2017

2017
[17]

Nikiforov, Some new results in extremal graph theory, inSurveys in combinatorics 2011, 141–181, London Math

V. Nikiforov, Some new results in extremal graph theory, inSurveys in combinatorics 2011, 141–181, London Math. Soc. Lecture Note Ser., 392, Cambridge Univ. Press, Cambridge

2011
[18]

Ollivier, Ricci curvature of Markov chains on metric spaces, J

Y. Ollivier, Ricci curvature of Markov chains on metric spaces, J. Funct. Anal. 256 (2009), no. 3, 810-864. 19

2009

[1] [1]

Ollivier Ricci curvature on graphs obtained by removing edges from complete graphs

Y. Asai and T. Yamada, Ollivier Ricci curvature on graphs obtained by removing edges from complete graphs, arXiv preprint arXiv:2605.30830 (2026)

work page internal anchor Pith review Pith/arXiv arXiv 2026

[2] [2]

Bakry and M

D. Bakry and M. Émery, Diffusions hypercontractives, Séminaire de probabilités, XIX, 1983/84, 177–206, Lecture Notes in Math. 1123, Springer, Berlin, 1985

1983

[3] [3]

Bollobás,Extremal graph theory, reprint of the 1978 original, Dover, Mineola, NY, 2004

B. Bollobás,Extremal graph theory, reprint of the 1978 original, Dover, Mineola, NY, 2004

1978

[4] [4]

D. P. Bourne, D. Cushing, S. Liu, F. Münch and N. Peyerimhoff, Ollivier-Ricci idleness functions of graphs, SIAM J. Discrete Math. 32(2) (2018) 1408-1424

2018

[5] [5]

K. Chen, S. Liu, Z. You, Connectivity versus Lin–Lu–Yau curvature, Int. Math. Res. Not., 19 (2025), rnaf303

2025

[6] [6]

K. Chen, S. Liu, Z. You, Criteria on forbidden subgraphs in the complements for positive Lin–Lu–Yau curvature, arXiv preprint arXiv: 2605.03470 (2026)

work page internal anchor Pith review Pith/arXiv arXiv 2026

[7] [7]

Cushing, S

D. Cushing, S. Kamtue, J. H. Koolen, S. Liu, F. Münch, N. Peyerimhoff, Rigidity of the Bonnet-Myers inequality for graphs with respect to Ollivier Ricci curvature, Adv. Math. 369 (2020), 107188

2020

[8] [8]

Cushing, R

D. Cushing, R. Kangaslampi, V. Lipiäinen, S. Liu and G. W. Stagg, The graph cur- vature calculator and the curvatures of cubic graphs, Exp. Math. 31 (2022), no. 2, 583-595

2022

[9] [9]

K.Devriendt, R.Lambiotte, Discretecurvatureongraphsfromtheeffectiveresistance, J. Phys. Complex. 3 (2) (2022) 025008

2022

[10] [10]

Füredi and M

Z. Füredi and M. Simonovits, The history of degenerate (bipartite) extremal graph problems, inErdös centennial, 169–264, Bolyai Soc. Math. Stud., 25, János Bolyai Math. Soc., Budapest

[11] [11]

1, Paper No

M.Hehl, RegulargraphswithpositiveOllivier-Riccicurvature, Math.Ann.394(2026), no. 1, Paper No. 24, 28 pp

2026

[12] [12]

Y. Li, W. J. Liu and L. H. Feng, A survey on spectral conditions for some extremal graph problems, Adv. Math. (China)51(2022), no. 2, 193–258

2022

[13] [13]

Y. Lin, L. Lu and S.-T. Yau, Ricci curvature of graphs, Tohoku Math. J. 63 (2011), no. 4, 605-627

2011

[14] [14]

Lin and S.-T

Y. Lin and S.-T. Yau, Ricci curvature and eigenvalue estimate on locally finite graphs, Math. Res. Lett. 17 (2010), no. 2, 343-356. 18

2010

[15] [15]

Münch and R

F. Münch and R. Wojciechowski, Ollivier Ricci curvature for general graph Laplacians: heatequation, Laplaciancomparison, non-explosionanddiameterbounds, Adv.Math. 356 (2019), 106759, 45 pp

2019

[16] [16]

Najman and P

L. Najman and P. Romon (Eds), Modern approaches to discrete curvature, Lecture Notes in Math., 2184, Springer, Cham, 2017

2017

[17] [17]

Nikiforov, Some new results in extremal graph theory, inSurveys in combinatorics 2011, 141–181, London Math

V. Nikiforov, Some new results in extremal graph theory, inSurveys in combinatorics 2011, 141–181, London Math. Soc. Lecture Note Ser., 392, Cambridge Univ. Press, Cambridge

2011

[18] [18]

Ollivier, Ricci curvature of Markov chains on metric spaces, J

Y. Ollivier, Ricci curvature of Markov chains on metric spaces, J. Funct. Anal. 256 (2009), no. 3, 810-864. 19

2009