pith. sign in

arxiv: 2605.03470 · v1 · submitted 2026-05-05 · 🧮 math.CO · math.DG

Criteria on forbidden subgraphs in the complements for positive Lin--Lu--Yau curvature

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

Pith reviewed 2026-05-07 15:50 UTC · model grok-4.3

classification 🧮 math.CO math.DG
keywords Lin-Lu-Yau curvaturegraph complementsforbidden subgraphspositive curvatureC4-free graphsK_{2,t}-free graphsdiscrete curvature
0
0 comments X

The pith

Every graph whose complement contains no 4-cycles has positive Lin-Lu-Yau curvature, except the 4-vertex path.

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

The paper establishes forbidden-subgraph conditions on the complement of a graph that force the original graph to have positive Lin-Lu-Yau curvature. It proves that a complement free of 4-cycles is enough to guarantee positivity on all graphs except the path with four vertices. It further shows that, once a graph is large enough, a complement free of any K_{2,t} also forces positive curvature. The authors supply matching lower bounds on graph size for the K_{2,t} case and counter-examples showing that longer cycles or denser bipartite forbidden subgraphs do not work.

Core claim

Every graph whose complement contains no 4-cycles has positive Lin-Lu-Yau curvature, with the only exception of the 4-vertex path. For any integer t≥2, every graph on at least max{t²-2t+2, 8t} vertices whose complement contains no K_{2,t} has positive curvature, and this lower bound on the number of vertices is optimal for t≥10. Examples show that cycles other than 4 and complete bipartite graphs K_{s,t} with s>2 cannot replace these forbidden subgraphs.

What carries the argument

Forbidden subgraphs (C4 and K_{2,t}) in the complement graph, which control the local degree and neighborhood overlap used to compute Lin-Lu-Yau curvature on each edge.

If this is right

  • Any graph whose complement is C4-free has positive Lin-Lu-Yau curvature except the path on four vertices.
  • For each t≥2, graphs larger than the stated threshold with K_{2,t}-free complements have positive curvature.
  • The vertex-size threshold is tight for every t≥10.
  • Forbidding longer cycles or K_{s,t} with s>2 in the complement does not guarantee positive curvature.

Where Pith is reading between the lines

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

  • The single exception of the 4-vertex path indicates that small graphs require separate verification even under strong complement conditions.
  • The optimality statement for t≥10 suggests that any improvement in the size bound would require a different forbidden subgraph.
  • The counter-examples delimit exactly which bipartite forbidden subgraphs are effective for curvature positivity.

Load-bearing premise

The results assume the standard definition of Lin-Lu-Yau curvature on finite undirected simple graphs together with the ordinary notion of graph complement.

What would settle it

A graph on more than max{t²-2t+2,8t} vertices whose complement contains no K_{2,t} yet has non-positive Lin-Lu-Yau curvature on at least one edge, or any graph other than the 4-vertex path whose complement contains no 4-cycle yet has negative curvature.

Figures

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

Figure 1
Figure 1. Figure 1: A schematic of the graph G. Choose a = ⌈ n 2 ⌉, b = ⌊ n 2 ⌋ − 3, c = 1, d = 0. Then, we have κLLY (x, y) ≤ 0. Then every cycle in G has length 4. This shows that Theorem 1.1 cannot be generalized by forbidding cycles of length k in the complement graph for any k = 3 or k > 4. Moreover, the complement of G contains no Ks,t with s > 2 and t > 2. Therefore, Theorem 1.2 cannot be generalized by forbidding Ks,t… view at source ↗
read the original abstract

We investigate forbidden subgraph conditions in the complement of a graph that guarantee positive Lin--Lu--Yau curvature. In particular, we prove that every graph whose complement contains no $4$-cycles has positive Lin--Lu--Yau curvature, with the only exception of the $4$-vertex path. We further prove that, for any integer $t\ge2$, every graph on at least $\max\{t^2-2t+2, 8t\}$ vertices whose complement contains no $K_{2,t}$ has positive curvature. In addition, this lower bound on the number of vertices is optimal for $t\geq 10$. Finally, we construct examples showing that, in general, the forbidden subgraphs in these results cannot be replaced by cycles of length other than $4$ or by complete bipartite graphs $K_{s,t}$ with $s> 2$ and $t> 2$.

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.

Referee Report

0 major / 2 minor

Summary. The manuscript establishes criteria based on forbidden subgraphs in the complement graph that guarantee positive Lin-Lu-Yau curvature. It proves that any graph whose complement is free of 4-cycles has positive curvature, except for the 4-vertex path. Additionally, for t ≥ 2, graphs with sufficiently many vertices (at least max{t²-2t+2, 8t}) whose complements contain no K_{2,t} have positive curvature, and this vertex lower bound is shown to be optimal for t ≥ 10. The paper also includes constructions demonstrating that these forbidden subgraphs cannot be generalized to other cycles or to K_{s,t} with s > 2.

Significance. If the proofs hold, the results provide valuable combinatorial characterizations for positive discrete curvature, which may aid in classifying graphs with positive curvature and understanding their structural properties. The optimality of the bounds and the negative results for other subgraphs enhance the sharpness of the findings. This contributes to the growing literature on discrete Ricci curvatures in graph theory.

minor comments (2)
  1. [Introduction] Recall or reference the precise definition of Lin-Lu-Yau curvature (including the role of the parameter p) at the start of the introduction or in a preliminary section to aid readers.
  2. [Section on K_{2,t}-free complements] Verify that all curvature computations in the proofs of the main theorems are presented with explicit intermediate steps for the boundary cases near the vertex threshold.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of our manuscript and for recommending minor revision. The referee's description accurately captures our main results on forbidden subgraphs in the complement guaranteeing positive Lin-Lu-Yau curvature, including the optimality statements and the negative results for other subgraphs.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper establishes combinatorial implications from forbidden subgraphs (C4 or K_{2,t}) in the complement to positive Lin-Lu-Yau curvature on finite simple undirected graphs, with explicit exceptions and optimality via constructions. These are direct proofs from the standard curvature definition (involving degrees and common neighbors) and graph-theoretic counting arguments; no parameters are fitted, no quantities are defined in terms of the claimed results, and no load-bearing steps reduce to self-citations or ansatzes. The vertex lower bound is shown sharp by explicit examples, which are independent of the main implication. The derivation chain is self-contained against the given definitions and does not collapse by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper introduces no free parameters, new entities, or ad-hoc axioms beyond the standard definition of Lin-Lu-Yau curvature and ordinary graph theory.

axioms (2)
  • domain assumption Standard definition and basic properties of Lin-Lu-Yau curvature on undirected graphs
    The positivity statements are proved relative to this established definition.
  • standard math Basic facts about graph complements and forbidden induced subgraphs
    These are invoked throughout the combinatorial arguments.

pith-pipeline@v0.9.0 · 5461 in / 1466 out tokens · 94739 ms · 2026-05-07T15:50:25.245922+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

  1. [1]

    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

    work page 2018

  2. [2]

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

    work page 2025

  3. [3]

    Cushing and A

    D. Cushing and A. J. Stone, A note on non-regular Bonnet-Myers sharp graphs, arXiv: 2405.04703, 2024

    work page arXiv 2024

  4. [4]

    Diestel,Graph theory, fifth edition, Graduate Texts in Mathematics, 173, Springer, Berlin, 2017

    R. Diestel,Graph theory, fifth edition, Graduate Texts in Mathematics, 173, Springer, Berlin, 2017. 14

    work page 2017

  5. [5]

    1, Paper No

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

    work page 2026

  6. [6]

    Hehl, A condition for non-negative Lin–Lu–Yau curvature, arXiv: 2502.03896, 2025

    M. Hehl, A condition for non-negative Lin–Lu–Yau curvature, arXiv: 2502.03896, 2025

    work page arXiv 2025

  7. [7]

    Huang, W

    Q. Huang, W. He and C. Zhang, Graphs with positive Ricci curvature, Graphs Com- bin. 41 (2025), no. 1, Paper No. 14, 13 pp

    work page 2025

  8. [8]

    Lin and Z

    H. Lin and Z. You, Graphs with positive Lin–Lu–Yau curvature without quadrilateral, arXiv: 2410.21887, 2024

    work page arXiv 2024

  9. [9]

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

    work page 2011

  10. [10]

    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

    work page 2019

  11. [11]

    Najman and P

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

    work page 2017

  12. [12]

    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. 15

    work page 2009