pith. sign in

arxiv: 2407.01625 · v2 · pith:Z26X2JSDnew · submitted 2024-06-29 · 🧮 math.CO

Balanced clique subdivisions and cycles lengths in K_(s, t)-free graphs

Jianfeng Hou , Yindong Jin , Donglei Yang , Fan Yang This is my paper

Pith reviewed 2026-05-23 23:18 UTC · model grok-4.3

classification 🧮 math.CO
keywords K_{s,t}-free graphsbalanced clique subdivisioncycle length reciprocalsaverage degreesublinear expansionextremal graph theoryMader conjecture
0
0 comments X

The pith

K_{s,t}-free graphs with average degree d contain balanced clique subdivisions of size Ω(d^{s/(2(s-1))}).

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

The paper shows that every K_{s,t}-free graph with average degree d has a balanced subdivision of a clique with at least Ω(d^{s/(2(s-1))}) vertices. A balanced subdivision is one in which every edge of the clique is subdivided the same number of times. It also proves that the sum of the reciprocals of the lengths of all cycles in the graph is at least (s/(2(s-1)) - o_d(1)) log d. This improves on a prior result that guaranteed only an ordinary subdivision and a weaker lower bound of (1/2 - o_d(1)) log d on the reciprocal sum. The proofs use the sublinear expansion property of the graph along with new structural techniques.

Core claim

Every K_{s,t}-free graph with average degree d contains a balanced subdivision of a clique with Ω(d^{s/(2(s-1))}) vertices. The sum of reciprocals of cycle lengths is at least (s/(2(s-1)) - o_d(1)) log d.

What carries the argument

Sublinear expansion property combined with novel structural techniques to enforce equal subdivision lengths on all edges of the target clique.

If this is right

  • Such graphs contain subdivisions that are balanced, allowing for uniform path lengths in the clique structure.
  • The cycle structure is dense enough that the harmonic sum of cycle lengths grows faster than the previous 1/2 exponent.
  • This provides a stronger confirmation of the subdivision size in Mader's conjecture for the balanced case.

Where Pith is reading between the lines

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

  • The method could be adapted to obtain balanced subdivisions in other classes of graphs with forbidden subgraphs.
  • Constructing extremal K_{s,t}-free graphs that achieve only smaller balanced subdivisions would test the tightness of the exponent.
  • Improved cycle bounds may help in analyzing the girth or cycle distributions in sparse graphs without dense bipartite subgraphs.

Load-bearing premise

The novel structural techniques combined with the sublinear expansion property are sufficient to produce a balanced subdivision rather than an arbitrary one.

What would settle it

A K_{s,t}-free graph with average degree d that has no balanced clique subdivision larger than o(d^{s/(2(s-1))}) vertices, or whose sum of reciprocal cycle lengths is smaller than (s/(2(s-1)) - o(1)) log d.

Figures

Figures reproduced from arXiv: 2407.01625 by Donglei Yang, Fan Yang, Jianfeng Hou, Yindong Jin.

Figure 3.1
Figure 3.1. Figure 3.1: An (h0, h1, h2, h3)-unit with h0 = 3 and h1 = h2 = 2, an (h1, h2)-hub with h1 = h2 = 2. Definition 3.2. (Unit [24]) Given integers h0, h1, h2, h3 > 0, an (h0, h1, h2, h3)-unit M is a graph con￾sisting of a core vertex v, h0 vertex-disjoint (h1, h2)-hubs H(v1), . . . , H(vh0 ) and pairwise disjoint (v, uj)- paths of length at most h3. By the exterior of the unit, denoted Ext(M), we mean Sh0 j=1 S 2(uj). D… view at source ↗
read the original abstract

Let $ t\ge s\ge2$ be integers. Confirming a conjecture of Mader, Liu and Montgomery [J. Lond. Math. Soc., 2017] showed that every $K_{s, t}$-free graph with average degree $d$ contains a subdivision of a clique with at least $\Omega(d^{\frac{s}{2(s-1)}})$ vertices. We give an improvement by showing that such a graph contains a balanced subdivision of a clique with the same order, where a balanced subdivision is a subdivision in which each edge is subdivided the same number of times. In 1975, Erd\H{o}s asked whether the sum of the reciprocals of the cycle lengths in a graph with infinite average degree $d$ is necessarily infinite. Recently, Liu and Montgomery [J. Amer. Math. Soc., 2023] confirmed the asymptotically correct lower bound on the reciprocals of the cycle lengths, and provided a lower bound of at least $(\frac{1}{2} -o_d(1)) \log d$. In this paper, we improve this low bound to $\left(\frac{s}{2(s-1)} -o_d(1)\right) \log d$ for $K_{s, t}$-free graphs. Both proofs of our results use the graph sublinear expansion property as well as some novel structural techniques.

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 paper proves two results for K_{s,t}-free graphs (t ≥ s ≥ 2) with average degree d. First, every such graph contains a balanced subdivision of a clique on Ω(d^{s/(2(s-1))}) vertices, strengthening the Liu-Montgomery theorem by requiring that each edge of the clique is subdivided the same number of times. Second, the sum of the reciprocals of all cycle lengths is at least (s/(2(s-1)) - o_d(1)) log d. Both proofs combine the sublinear expansion property with new structural techniques.

Significance. If correct, the results give a quantitatively stronger form of Mader's conjecture in the K_{s,t}-free setting and improve the best-known lower bound on cycle-reciprocal sums for this class of graphs. The balanced-subdivision guarantee is a strictly stronger conclusion than the earlier arbitrary-subdivision result and may enable further applications; the cycle bound is asymptotically sharper than the general-graph ½ log d bound when s is fixed.

minor comments (2)
  1. [title] The title contains the grammatical error 'cycles lengths'; it should read 'cycle lengths'.
  2. [abstract] Abstract, line 8: 'low bound' should be 'lower bound'.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of our results on balanced clique subdivisions and cycle-reciprocal sums in K_{s,t}-free graphs, and for recommending minor revision. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained via novel techniques

full rationale

The paper cites Liu-Montgomery 2017 and 2023 for the base subdivision and cycle-reciprocal results but explicitly invokes new structural techniques (combined with sublinear expansion) to obtain the balanced-subdivision strengthening while keeping the same quantitative order. The cycle-length improvement is derived directly from the new subdivision result. No equations reduce by construction to fitted inputs, no load-bearing self-citation chains, and no ansatz or uniqueness theorem imported from the authors' own prior work. The central claims therefore contain independent content beyond the cited inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claims rest on the sublinear expansion property (domain assumption) and standard graph-theoretic axioms; no free parameters or invented entities are visible from the abstract.

axioms (2)
  • domain assumption Graphs satisfy the sublinear expansion property
    Invoked explicitly for both proofs in the final sentence of the abstract.
  • standard math Standard axioms and definitions of graph theory and subdivisions
    Background for all statements about K_{s,t}-free graphs, average degree, and subdivisions.

pith-pipeline@v0.9.0 · 5788 in / 1327 out tokens · 27954 ms · 2026-05-23T23:18:33.972933+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

40 extracted references · 40 canonical work pages

  1. [1]

    Balogh, H

    J. Balogh, H. Liu, M. Sharifzadeh, Subdivisions of a large clique in C6-free graphs. J. Combin. Theory Ser. B 112 (2015) 18–35. 17

    work page 2015

  2. [2]

    Bollob ´as, A

    B. Bollob ´as, A. Thomason, Proof of a conjecture of Mader, Erd ˝os and Hajnal on topological complete sub- graphs. Eur. J. Comb. 19 (1998) 883–887

    work page 1998

  3. [3]

    Bondy, A

    J. Bondy, A. Vince, Cycles in a graph whose lengths di ffer by one or two. J. Graph Theory 27 (1998) 11–15

    work page 1998

  4. [4]

    Erd ˝os, Some recent progress on extremal problems in graph theory

    P. Erd ˝os, Some recent progress on extremal problems in graph theory. Congr. Numer. 14 (1975) 3–14

    work page 1975

  5. [5]

    Erd ˝os, A

    P. Erd ˝os, A. Hajnal, On chromatic number of graphs and set-systems. Acta Math. Acad. Sci. Hungar. 17 (1966) 61–99

    work page 1966

  6. [6]

    Erd ˝os, A

    P. Erd ˝os, A. Hajnal, On topological complete subgraphs of certain graphs. Annales Univ. Sci. Budapest 7 (1969) 193–199

    work page 1969

  7. [7]

    Fan, Distribution of cycle lengths in graphs

    G. Fan, Distribution of cycle lengths in graphs. J. Combin. Theory Ser. B 84 (2002) 187–202

    work page 2002

  8. [8]

    Fern ´andez, J

    I. Fern ´andez, J. Hyde, H. Liu, P. Oleg, Z. Wu, Disjoint isomorphic balanced clique subdivisions. J. Combin. Theory Ser. B 161 (2023) 417–436

    work page 2023

  9. [9]

    J. Fox, B. Sudakov, Dependent random choice. Random Structures and Algorithms 38 (2011) 68–99

    work page 2011

  10. [10]

    Friedman, M

    L. Friedman, M. Krivelevich, Cycle lengths in expanding graphs. Combinatorica 41 (2021) 53–74

    work page 2021

  11. [11]

    F ¨uredi, An upper bound on Zarankiewicz’ problem

    Z. F ¨uredi, An upper bound on Zarankiewicz’ problem. Combin. Probab. Comput. 5 (1996) 29–33

    work page 1996

  12. [12]

    J. Gao, Q. Huo, C.-L. Liu, J. Ma, A unified proof of conjectures on cycle lengths in graphs. Int. Math. Res. Not. 2022 (2022) 7615–7653

    work page 2022

  13. [13]

    J. Gao, Q. Huo, J. Ma, A strengthening on odd cycles in graphs of given chromatic number. SIAM J. Discrete Math. 35 (2021) 2317–2327

    work page 2021

  14. [14]

    J. Gao, J. Ma, On a conjecture of Bondy and Vince. J. Combin. Theory Ser. B. 141 (2020) 136–142

    work page 2020

  15. [15]

    Gy ´arf´as, J

    A. Gy ´arf´as, J. Koml´os, E. Szemer´edi, On the distribution of cycle lengths in graphs. J. Graph Theory 8 (1984) 441–462

    work page 1984

  16. [16]

    Jiang, J

    T. Jiang, J. Ma, L. Yepremyan, Linear cycles of consecutive lengths. J. Combin. Theory Ser. B 163 (2023) 1–24

    work page 2023

  17. [17]

    K ¨ov´ari, V

    T. K ¨ov´ari, V . T. S´os, P. Tur´an, On a problem of K. Zarankiewicz, Colloq. Math. 3 (1954) 50–57

    work page 1954

  18. [18]

    Koml ´os, E

    J. Koml ´os, E. Szemer´edi, Topological cliques in graphs, Comb. Probab. Comput. 3 (1994) 247–256

    work page 1994

  19. [19]

    Koml ´os, E

    J. Koml ´os, E. Szemer´edi, Topological cliques in graphs II. Comb. Probab. Comput. 5 (1996) 79–90

    work page 1996

  20. [20]

    K ¨uhn, D

    D. K ¨uhn, D. Osthus, Topological minors in graphs of large girth. J. Combin. Theory Ser. B 86 (2002) 364– 380

    work page 2002

  21. [21]

    K ¨uhn, D

    D. K ¨uhn, D. Osthus, Improved bounds for topological cliques in graphs of large girth. SIAM J. Discrete Math. 20 (2006) 62–78

    work page 2006

  22. [22]

    K ¨uhn, D

    D. K ¨uhn, D. Osthus, Large topological cliques in graphs without a 4-cycle. Comb. Probab. Comput. 13 (2004) 93–102

    work page 2004

  23. [23]

    Kuratowski, Sur le probleme des courbes gauches en topologie

    J. Kuratowski, Sur le probleme des courbes gauches en topologie. Fundam. Math. 16 (1930) 271–283

    work page 1930

  24. [24]

    H. Liu, R. Montgomery, A proof of Mader’s conjecture on large clique subdivisions in C4-free graphs. J. Lond. Math. Soc. 95 (2017) 203–222

    work page 2017

  25. [25]

    H. Liu, R. Montgomery, A solution to Erd ˝os and Hajnal’s odd cycle problem. J. Amer. Math. Soc. 36 (2023) 1191–1234

    work page 2023

  26. [26]

    B. Luan, Y . Tang, G. Wang, D. Yang, Balanced Subdivisions of Cliques in Graphs. Combinatorica 43 (2023) 885–907

    work page 2023

  27. [27]

    Ma, Cycles with consecutive odd lengths

    J. Ma, Cycles with consecutive odd lengths. Eur. J. Comb. 52 (2016) 74–78. 18

    work page 2016

  28. [28]

    Mader, Homomorphieeigenschaften und mittlere Kantendichte von Graphen

    W. Mader, Homomorphieeigenschaften und mittlere Kantendichte von Graphen. Math. Ann. 174 (1967) 265– 268

    work page 1967

  29. [29]

    W. Mader. Hinreichende Bedingungen f ˝ur die Existenz von Teilgraphen, die zu einem vollst˝andigen Graphen hom˝oomorph sind. Math. Nachr. 53 (1972) 145–150

    work page 1972

  30. [30]

    Mader, An extremal problem for subdivisions of K− 5

    W. Mader, An extremal problem for subdivisions of K− 5 . J. Graph Theory 30 (1999) 261–276

    work page 1999

  31. [31]

    Sudakov, J

    B. Sudakov, J. Verstra ¨ete. Cycle lengths in sparse graphs. Combinatorica 28 (2008) 357–372

    work page 2008

  32. [32]

    Thomassen, Subdivisions of graphs with large minimum degree

    C. Thomassen, Subdivisions of graphs with large minimum degree. J. Graph Theory. 8 (1984) 23–28

    work page 1984

  33. [33]

    Thomassen, Problems 20 and 21, in Graphs, Hypergraphs and Applications

    C. Thomassen, Problems 20 and 21, in Graphs, Hypergraphs and Applications. H. Sachs, ed., 217 , Teubner. Leipzig (1985)

    work page 1985

  34. [34]

    Thomason, Configurations in graphs of large minimum degree, connectivity, or chromatic number

    C. Thomason, Configurations in graphs of large minimum degree, connectivity, or chromatic number. Ann. N. Y . Acad. Sci. 1 (1989) 402–412

    work page 1989

  35. [35]

    Verstra ¨ete, On arithmetic progressions of cycle lengths in graphs

    J. Verstra ¨ete, On arithmetic progressions of cycle lengths in graphs. Combin. Probab. Comput. 9 (2000) 369–373

    work page 2000

  36. [36]

    Wang, Balanced Subdivisions of a large clique in graphs with high average degree

    Y . Wang, Balanced Subdivisions of a large clique in graphs with high average degree. SIAM J. Discrete Math. 37 (2023) 1262–1274. A Proofs of Lemmas 3.7 and 3.12 In this section, we mainly complete the proof of Lemma 3.7. The proof of Lemma 3.12 is similar to the proof Lemma 3.7, the sight difference is when prove Lemma 3.12, we use a unit (whose existenc...

    work page 2023

  37. [37]

    Applying Lemma B.1 with W ′ = W, we have d(G − W ′) ≥ d/2, and by Corollary 2.4 with G = G − W ′, there exists a bipartite (ε1, ε2η)- expander H ⊆ G − W ′ with δ(H) ≥ d

    · m240 ≤ η2m240 30t . Applying Lemma B.1 with W ′ = W, we have d(G − W ′) ≥ d/2, and by Corollary 2.4 with G = G − W ′, there exists a bipartite (ε1, ε2η)- expander H ⊆ G − W ′ with δ(H) ≥ d

    work page

  38. [38]

    Arbitrarily pick two vertices v1, v2 ∈ V(C) of distance r − 1 on C

    Thus, there exists a shortest cycle C in G′ of length at most m4 16 and we denoted by 2r the length of C. Arbitrarily pick two vertices v1, v2 ∈ V(C) of distance r − 1 on C. Since δ(H) ≥ d 16, we can find a subset Ai ⊂ NH−C(vi) of size d 400 for each i ∈ [2] such that A1 ∩ A2 = ∅. Let B1 = NH−C(A1)\A2 and B2 = NH−C(A2)\A1. Note that G[Ai, Bi] does not con...

    work page

  39. [39]

    Then by Proposition 3.4, there exists a subgraph of F′ 2, denoted by F2, which is a ( η2m20, m4/2)-expansion of v2

    is at most m4 600 + m4 6 + m4 600 + m4 32 + m4 600 ≤ m4/2. Then by Proposition 3.4, there exists a subgraph of F′ 2, denoted by F2, which is a ( η2m20, m4/2)-expansion of v2. Similarly, we can find F1, which is a ( η2m20, m4/2)-expansion of v1. Recall that Ck ∪ {v1, v2} is an even cycle of length 2r0 ≤ m4 16 , and the distance between v1 and v2 on Ck ∪ {v...

    work page

  40. [40]

    Then, by Corollary 2.4, G − U − W ′ contains an (ε1, ε2 ¯d)-expander H with δ(H) ≥ ¯d

    As G − U contains at least nd/8 edges, G − U − W ′ contains at least nd 16 edges, so that d(G − U − W ′) ≥ d/8 = 8 ¯d. Then, by Corollary 2.4, G − U − W ′ contains an (ε1, ε2 ¯d)-expander H with δ(H) ≥ ¯d. Let C be a shortest cycle in H. We will consider two cases, depending on how many vertices of L there are in V(H)\V(C). The first case is that |(V(H)\V...

    work page