pith. sign in

arxiv: 2604.17595 · v1 · submitted 2026-04-19 · 🧮 math.CO

Fundamental cycles in grid graphs

Bart{\l}omiej Kielak , Daniel Kr\'al' , Ander Lamaison , Xichao Shu This is my paper

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

classification 🧮 math.CO
keywords fundamental cyclesspanning treesgrid graphscycle lengthsbinary matroidsmatroid representationslower boundsaverage length
0
0 comments X

The pith

For any spanning tree of the n by n grid graph, the average length of its fundamental cycles is at least logarithmic in n.

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

The paper proves that in the n by n square grid graph, every spanning tree forces the average length of the fundamental cycles to be at least on the order of log n. A fundamental cycle arises when an edge outside the tree is added back, closing a unique cycle with the tree path. The lower bound is obtained by averaging over all such cycles and using the grid's row-column structure to show that many long paths must appear. The same bound is shown to be tight because certain spanning trees achieve an average of O(log n). The result settles an open question on the sparsity of representations for binary matroids.

Core claim

We show that the average length of a fundamental cycle with respect to any fixed spanning tree of the n×n square grid is at least Ω(log n); the bound is asymptotically tight. This result answers in the affirmative a question posed by McCarty in relation to sparse representations of binary matroids.

What carries the argument

Averaging argument that sums lengths of all fundamental cycles induced by the non-tree edges and divides by their number, using the grid's bipartition and path-counting to obtain a logarithmic lower bound independent of tree choice.

If this is right

  • No spanning tree can keep the average fundamental cycle length below logarithmic order.
  • The lower bound holds uniformly for every spanning tree, not just for some special trees.
  • There exist spanning trees achieving an average of Theta(log n), so the bound cannot be strengthened asymptotically.
  • Sparse representations of the cycle matroid of the grid graph cannot avoid a logarithmic density factor.

Where Pith is reading between the lines

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

  • The same averaging technique may yield logarithmic lower bounds on cycle lengths for spanning trees in higher-dimensional grids or other lattice graphs.
  • Algorithms that search for short-cycle spanning trees in grids will face an inherent logarithmic barrier on the average.
  • In matroid language, the grid implies that any representation of its binary cycle matroid must contain a logarithmic fraction of long circuits.

Load-bearing premise

That the standard definitions of spanning trees and fundamental cycles in the n by n grid graph permit an averaging argument that produces the stated Omega(log n) lower bound for every spanning tree.

What would settle it

Exhibiting a single spanning tree in a large n by n grid whose fundamental cycles have average length o(log n).

Figures

Figures reproduced from arXiv: 2604.17595 by Ander Lamaison, Bart{\l}omiej Kielak, Daniel Kr\'al', Xichao Shu.

Figure 1
Figure 1. Figure 1: The spanning trees T2 and T3 constructed in the proof of Theorem 1; the positions of the vertices in the figure determine the trees. The root vertex is depicted by the empty circle and the edges not contained in the tree are omitted. the bottom path of the grid, the edges forming the central vertical path, and four copies of T(n−1)/2 tiling the rest in the grid. The two copies of T(n−1)/2 to the right from… view at source ↗
Figure 2
Figure 2. Figure 2: Illustration of the construction of the spanning tree [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The spanning trees T4 and T5 constructed in the proof of Theorem 1. the positions of the vertices in the figure determine the trees. The root vertex is depicted by the empty circle and the edges not contained in the tree are omitted. 5 [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: An expanded 5-grid. The duplicate vertices are drawn with empty [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: A 6-grid H with a spanning tree T (drawn in the left) and the expanded grid H[G′/T] (drawn in the right) where G′ is the subgrid with the vertices drawn by empty circles. The edges of the spanning tree T and the edges of the resulting spanning tree in H[G′/T] are drawn in bold. associated with the edges of the host grid of H that are not contained in T. Let H be an expanded grid, T a spanning tree of H and… view at source ↗
Figure 6
Figure 6. Figure 6: The tiling of the host 25-grid with the 5-grids [PITH_FULL_IMAGE:figures/full_fig_p009_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: The cycles C1, . . . , C5 in the host 25-grid as defined in the proof of Theorem 4; the cycles are drawn using the bold edges. 11 [PITH_FULL_IMAGE:figures/full_fig_p011_7.png] view at source ↗
read the original abstract

We show that the average length of a fundamental cycle with respect to any fixed spanning tree of the $n\times n$ square grid is at least $\Omega(\log n)$; the bound is asymptotically tight. This result answers in the affirmative a question posed by McCarty in relation to sparse representations of binary matroids.

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 proves that for any spanning tree T of the n×n grid graph, the average length of the fundamental cycles (i.e., 1 + dist_T(u,v) averaged over all chords uv) is Ω(log n). The bound is shown to be tight by exhibiting a quadtree-style spanning tree that achieves O(log n). The argument relies on a potential-function or contradiction counting that exploits the grid's recursive quadrant decomposition.

Significance. The result affirmatively resolves McCarty's question on sparse representations of binary matroids. The elementary, self-contained proof via quadrant recursion and the matching construction are strengths; the work gives a clean structural fact about cycle spaces in grid graphs with no hidden parameters or uniformity assumptions.

minor comments (2)
  1. In the introduction, briefly recall the precise definition of fundamental cycle length (1 + dist_T(u,v)) before stating the average; this will aid readers coming from matroid theory.
  2. Add a short paragraph or figure illustrating the quadtree construction for n=4 or n=8 to make the O(log n) upper bound more immediately visible.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive report, accurate summary of the main result, and recommendation to accept the manuscript. The work resolves McCarty's question on sparse representations of binary matroids via an elementary quadrant-recursion argument and matching quadtree construction.

Circularity Check

0 steps flagged

No circularity; direct self-contained combinatorial argument

full rationale

The manuscript derives the Ω(log n) lower bound on average fundamental-cycle length for any spanning tree T of the n×n grid via an elementary counting argument that exploits the grid's recursive quadrant decomposition and the necessary existence of long-distance chords in any spanning tree. The matching O(log n) upper bound is obtained by exhibiting an explicit quadtree-style tree. No parameter is fitted to data, no quantity is defined in terms of the target bound, and no load-bearing step reduces to a self-citation or prior result by the same authors. All steps are first-principles and externally verifiable from the grid graph definition alone.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on standard graph-theoretic definitions without introducing free parameters or new entities.

axioms (1)
  • standard math Basic properties of undirected graphs, spanning trees, and the uniqueness of the cycle formed by adding a chord to a tree.
    These definitions are invoked to define fundamental cycles and their lengths.

pith-pipeline@v0.9.0 · 5340 in / 1178 out tokens · 51468 ms · 2026-05-10T05:24:25.151642+00:00 · methodology

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

45 extracted references · 45 canonical work pages

  1. [1]

    Aschenbrenner and R

    M. Aschenbrenner and R. Hemmecke:Finiteness theorems in stochas- tic integer programming, Foundations of Computational Mathematics7 (2007), 183–227

    work page 2007

  2. [2]

    Aykanat, A

    C. Aykanat, A. Pinar and ¨U. V. C ¸ ataly¨ urek:Permuting sparse rect- angular matrices into block-diagonal form, SIAM Journal on Scientific Computing25(2004), 1860–1879

    work page 2004

  3. [3]

    Bergner, A

    M. Bergner, A. Caprara, A. Ceselli, F. Furini, M. E. L¨ ubbecke, E. Malaguti and E. Traversi:Automatic Dantzig–Wolfe reformulation of mixed integer programs, Mathematical Programming149(2015), 391– 424

    work page 2015

  4. [4]

    Bornd¨ orfer, C

    R. Bornd¨ orfer, C. E. Ferreira and A. Martin:Decomposing matrices into blocks, SIAM Journal on Optimization9(1998), 236–269. 13

    work page 1998

  5. [5]

    Bria´ nski, M

    M. Bria´ nski, M. Kouteck´ y, D. Kr´ al’, K. Pek´ arkov´ a and F. Schr¨ oder: Characterization of Matrices with Bounded Graver Bases and Depth Pa- rameters and Applications to Integer Programming, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) (2022), 29:1–29:20

    work page 2022

  6. [6]

    Bria´ nski, M

    M. Bria´ nski, M. Kouteck´ y, D. Kr´ al’, K. Pek´ arkov´ a and F. Schr¨ oder: Characterization of matrices with bounded graver bases and depth pa- rameters and applications to integer programming, Mathematical Pro- gramming208(2024), 497–531

    work page 2024

  7. [7]

    T. F. Chan, J. W. Cooper, M. Kouteck´ y, D. Kr´ al and K. Pek´ arkov´ a: Matrices of optimal tree-depth and a row-invariant parameterized algo- rithm for integer programming, SIAM Journal on Computing51(2022), 664–700

    work page 2022

  8. [8]

    T. F. N. Chan, J. W. Cooper, M. Kouteck´ y, D. Kr´ al’ and K. Pek´ arkov´ a: Matrices of Optimal Tree-Depth and Row-Invariant Parameterized Al- gorithm for Integer Programming, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) (2020), 26:1– 26:19

    work page 2020

  9. [9]

    Chen and D

    L. Chen and D. Marx:Covering a tree with rooted subtrees– parameterized and approximation algorithms, 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2018, 2801–2820

    work page 2018

  10. [10]

    Courcelle:The monadic second-order logic of graphs

    B. Courcelle:The monadic second-order logic of graphs. I. recognizable sets of finite graphs, Inform. and Comput.85(1990), 12–75

    work page 1990

  11. [11]

    Courcelle, J

    B. Courcelle, J. A. Makowsky and U. Rotics:Linear time solvable opti- mization problems on graphs of bounded clique-width, Theory Comput. Syst.33(2000), 125–150

    work page 2000

  12. [12]

    Cslovjecsek, F

    J. Cslovjecsek, F. Eisenbrand, C. Hunkenschr¨ oder, L. Rohwedder and R. Weismantel:Block-structured integer and linear programming in strongly polynomial and near linear time, 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2021, 1666–1681

    work page 2021

  13. [13]

    Cslovjecsek, F

    J. Cslovjecsek, F. Eisenbrand, M. Pilipczuk, M. Venzin and R. Weisman- tel:Efficient sequential and parallel algorithms for multistage stochastic integer programming using proximity, 29th Annual European Sympo- sium on Algorithms (ESA), LIPIcs vol. 204 (2021), 33:1–33:14. 14

    work page 2021

  14. [14]

    J. A. De Loera, R. Hemmecke, S. Onn and R. Weismantel:N-fold integer programming, Discrete Optimization5(2008), 231–241

    work page 2008

  15. [15]

    Dvoˇ r´ ak, D

    Z. Dvoˇ r´ ak, D. Kr´ al’ and R. Thomas:Deciding first-order properties for sparse graphs, 51th IEEE Annual Symposium on Foundations of Computer Science, FOCS (2010), 133–142

    work page 2010

  16. [16]

    Dvoˇ r´ ak, D

    Z. Dvoˇ r´ ak, D. Kr´ al’ and R. Thomas:Testing first-order properties for subclasses of sparse graphs, Journal of the ACM60(2013), 24:1–36

    work page 2013

  17. [17]

    Eisenbrand, C

    F. Eisenbrand, C. Hunkenschr¨ oder and K.-M. Klein:Faster algorithms for integer programs with block structure, 45th International Colloquium on Automata, Languages, and Programming (ICALP), LIPIcs vol. 107 (2018), 49:1–49:13

    work page 2018

  18. [18]

    M. C. Ferris and J. D. Horn:Partitioning mathematical programs for parallel solution, Mathematical Programming80(1998), 35–61

    work page 1998

  19. [19]

    Frick and M

    M. Frick and M. Grohe:Deciding first-order properties of locally tree- decomposalbe graphs, in: 26th International Colloquium on Automata, Languages, and Programming (ICALP),Lecture Notes in Computer Sci- ence, volume 1644 (1999), 331–340

    work page 1999

  20. [20]

    Frick and M

    M. Frick and M. Grohe:Deciding first-order properties of locally tree- decomposable structures, Journal of the ACM48(2001), 1184–1206

    work page 2001

  21. [21]

    Gamrath and M

    G. Gamrath and M. E. L¨ ubbecke:Experiments with a generic Dantzig– Wolfe decomposition for integer programs, Experimental Algorithms 6049(2010), 239 – 252

    work page 2010

  22. [22]

    Ganian and S

    R. Ganian and S. Ordyniak:The complexity landscape of decomposi- tional parameters for ILP, Artificial Intelligence257(2018), 61–71

    work page 2018

  23. [23]

    Gavenˇ ciak, D

    T. Gavenˇ ciak, D. Kr´ al’ and S. Oum:Deciding first order properties of matroids, 39th International Colloquium Automata, Languages, and Programming, ICALP (2012), 239–250

    work page 2012

  24. [24]

    Grohe, S

    M. Grohe, S. Kreutzer and S. Siebertz:Deciding first-order properties of nowhere dense graphs, Proceedings of the 46th Annual ACM Symposium on Theory of computing, STOC (2014), 89–98

    work page 2014

  25. [25]

    Grohe, S

    M. Grohe, S. Kreutzer and S. Siebertz:Deciding first-order properties of nowhere dense graphs, Journal of the ACM64(2017), 37:1–32. 15

    work page 2017

  26. [26]

    Hemmecke, S

    R. Hemmecke, S. Onn and L. Romanchuk:N-fold integer programming in cubic time, Mathematical Programming137(2013), 325–341

    work page 2013

  27. [27]

    Hemmecke and R

    R. Hemmecke and R. Schultz:Decomposition of test sets in stochastic integer programming, Mathematical Programming94(2003), 323–341

    work page 2003

  28. [28]

    Hlinˇ en´ y:Branch-width, parse trees, and monadic second-order logic for matroids, 20th Annual Symposium on Theoretical Aspects of Com- puter Science (STACS), LNCS vol

    P. Hlinˇ en´ y:Branch-width, parse trees, and monadic second-order logic for matroids, 20th Annual Symposium on Theoretical Aspects of Com- puter Science (STACS), LNCS vol. 2607 (2003), 319–330

    work page 2003

  29. [29]

    Hlinˇ en´ y:On matroid properties definable in the MSO logic, 27th International Symposium on Mathematical Foundations of Computer Science, MFCS (2003), 470–479

    P. Hlinˇ en´ y:On matroid properties definable in the MSO logic, 27th International Symposium on Mathematical Foundations of Computer Science, MFCS (2003), 470–479

    work page 2003

  30. [30]

    Hlinˇ en´ y:Branch-width, parse trees, and monadic second-order logic for matroids, Journal of Combinatorial Theory Series B96(2006), 325– 351

    P. Hlinˇ en´ y:Branch-width, parse trees, and monadic second-order logic for matroids, Journal of Combinatorial Theory Series B96(2006), 325– 351

    work page 2006

  31. [31]

    Hlinˇ en´ y and S

    P. Hlinˇ en´ y and S. Oum:Finding branch-decompositions and rank- decompositions, 15th Annual European Symposium, ESA (2007), 163– 174

    work page 2007

  32. [32]

    Hlinˇ en´ y and S

    P. Hlinˇ en´ y and S. Oum:Finding branch-decompositions and rank- decompositions, SIAM Journal on Computing38(2008), 1012–1032

    work page 2008

  33. [33]

    Jansen, K

    K. Jansen, K. Klein and A. Lassota:The double exponential runtime is tight for 2-stage stochastic ILPs, Integer Programming and Combinato- rial Optimization - 22nd International Conference (IPCO), LNCS vol. 12707 (2021), 297–310

    work page 2021

  34. [34]

    Jansen, A

    K. Jansen, A. Lassota and L. Rohwedder:Near-linear time algorithm forn-fold ILPs via color coding, SIAM Journal on Discrete Mathematics 34(2020), 2282–2299

    work page 2020

  35. [35]

    Jeong, E

    J. Jeong, E. J. Kim and S. Oum:Finding Branch-Decompositions of Matroids, Hypergraphs, and More, 45th International Colloquium on Automata, Languages, and Programming, ICALP (2018), 80:1–80:14

    work page 2018

  36. [36]

    Khaniyev, S

    T. Khaniyev, S. Elhedhli and F. S. Erenay:Structure detection in mixed- integer programs, INFORMS Journal on Computing30(2018), 570–587

    work page 2018

  37. [37]

    Klein:About the complexity of two-stage stochastic IPs, to appear in Mathematical Programming

    K.-M. Klein:About the complexity of two-stage stochastic IPs, to appear in Mathematical Programming . 16

    work page

  38. [38]

    Klein and J

    K.-M. Klein and J. Reuter:Collapsing the tower - on the complexity of multistage stochastic IPs, 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2022, 348–358

    work page 2022

  39. [39]

    Kouteck´ y, A

    M. Kouteck´ y, A. Levin and S. Onn:A parameterized strongly polynomial algorithm for block structured integer programs, 45th International Col- loquium on Automata, Languages, and Programming (ICALP), LIPIcs vol. 107 (2018), 85:1–85:14

    work page 2018

  40. [40]

    McCarty:Sparse representations of binary matroids, The Ma- troid Union, A blog for and by the matroid community (2014)

    R. McCarty:Sparse representations of binary matroids, The Ma- troid Union, A blog for and by the matroid community (2014). https://matroidunion.org/?p=5526

    work page 2014

  41. [41]

    Neˇ setril and P

    J. Neˇ setril and P. Ossona de Mendez: Sparsity: Graphs, Structures, and Algorithms,Algorithms and Combinatorics, volume 28, Springer, 2012

    work page 2012

  42. [42]

    Seese:Linear time computable problems and first-order descriptions, Mathematical Structures in Computer Science6(1996), 505–526

    D. Seese:Linear time computable problems and first-order descriptions, Mathematical Structures in Computer Science6(1996), 505–526

    work page 1996

  43. [43]

    Vanderbeck and L

    F. Vanderbeck and L. A. Wolsey:Reformulation and decomposition of integer programs, in: 50 Years of Integer Programming 1958-2008 (2010), 431–502

    work page 1958

  44. [44]

    Wang and T

    J. Wang and T. Ralphs:Computational experience with hypergraph- based methods for automatic decomposition in discrete optimization (2013)

    work page 2013

  45. [45]

    R. L. Weil and P. C. Kettler:Rearranging matrices to block-angular form for decomposition (and other) algorithms, Management Science18 (1971), 98–108. 17

    work page 1971