pith. sign in

arxiv: 2603.20030 · v2 · pith:J6W22DNRnew · submitted 2026-03-20 · 💻 cs.CG · cs.DM· math.CO

On the size of k-irreducible triangulations

Vincent Delecroix , Oscar Fontaine , Arnaud de Mesmay This is my paper

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

classification 💻 cs.CG cs.DMmath.CO
keywords k-irreducible triangulationorientable surfacegenus gnon-contractible curveedge contractiontriangulation sizecombinatorial topology
0
0 comments X

The pith

A k-irreducible triangulation of a genus g surface has O(k² g) triangles.

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

The paper shows that k-irreducible triangulations of orientable surfaces stay small. Such a triangulation has every non-contractible curve at least length k, and contracting any edge creates a shorter non-contractible curve. The authors establish that the number of triangles is linear in the genus g and quadratic in k. This improves a previous bound that grew much faster in both parameters. A reader cares because the result gives a tight control on the size of these minimal topological representatives.

Core claim

We prove that a k-irreducible triangulation of an orientable surface of genus g has O(k²g) triangles, which is optimal. The proof first shows equivalence between the girth definition (no non-contractible curve shorter than k) and the covering definition (every edge lies on a non-contractible curve of length exactly k), then uses a sequence of edge contractions that preserve validity to reduce the triangulation and derive the size bound from topological properties of the surface.

What carries the argument

The equivalence of the two definitions of k-irreducibility, combined with girth-preserving edge contractions on orientable surfaces.

Load-bearing premise

The two definitions of k-irreducibility are equivalent and edge contractions that would create short non-contractible curves can still be performed while keeping a valid triangulation of the surface.

What would settle it

An explicit k-irreducible triangulation of genus g with more than C k² g triangles for a sufficiently large constant C would falsify the claimed bound.

Figures

Figures reproduced from arXiv: 2603.20030 by Arnaud de Mesmay, Oscar Fontaine, Vincent Delecroix.

Figure 1
Figure 1. Figure 1: The triangulation in blue, a walk in red, its corresponding noose in green and the [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: A smoothing at v A geodesic is a closed curve transverse to C and of minimal length within its homotopy class. For a given system of curves C, we say that a smoothing C ′ of C is geodesically k-covered if • there is a geodesic c of length at most k with respect to C, and • there is a curve c ′ homotopic to c and such that cr(c ′ , C ′ ) < cr(c, C). We say that a system of curves C on a surface S is geodesi… view at source ↗
Figure 3
Figure 3. Figure 3: A graph G in blue on a genus 2 surface and its medial graph in orange v(e) [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The contraction of an edge in G. The blue graph is G, the orange one is C and the red curve is c. associated to G. As cr(c, G) ⩾ k for every non-contractible curve c, cr(γ, C) = 2 cr(γ, G) ⩾ 2k for every non-trivial homotopy class γ. Let C ′ be a smoothing of C. As shown in [41], a smoothing of C either corresponds to an edge deletion or an edge contraction in G. We work separately on these two cases. 1. A… view at source ↗
Figure 5
Figure 5. Figure 5: Wedding of two curves s and s ′ . c˜2 c˜1 c˜ c˜3 s˜3 s˜4 c˜2 c˜1 c˜ c˜3 s˜3 s˜4 c˜2 c˜1 c˜3 c˜ s˜4 w˜1 w˜2 s˜1 [PITH_FULL_IMAGE:figures/full_fig_p011_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The three different cases leading to the proof of claim 4.5. [PITH_FULL_IMAGE:figures/full_fig_p011_6.png] view at source ↗
read the original abstract

A triangulation of a surface is k-irreducible if every non-contractible curve has length at least k and any edge contraction breaks this property. Equivalently, every edge belongs to a non-contractible curve of length k and there are no shorter non-contractible curves. We prove that a k-irreducible triangulation of an orientable surface of genus g has $O(k^2g)$ triangles, which is optimal. This is an improvement over the previous best bound $k^{O(k)} g^2$ of Gao, Richter and Seymour [Journal of Combinatorial Theory, Series B, 1996].

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

2 major / 2 minor

Summary. The manuscript proves that a k-irreducible triangulation of an orientable surface of genus g has O(k²g) triangles and that this bound is tight. The definition of k-irreducible is given in two equivalent forms: every non-contractible curve has length at least k and every edge contraction destroys this property, or equivalently every edge lies on a shortest non-contractible k-cycle. The proof improves the prior bound of k^{O(k)} g² from Gao, Richter and Seymour (1996) and relies on a charging argument via the Euler characteristic after establishing the equivalence.

Significance. If the central proof is correct, the result supplies a quadratic dependence on k that is asymptotically optimal and substantially sharper than the previous exponential-in-k bound. This has direct consequences for the complexity of minimal triangulations with controlled girth on surfaces and for algorithms that enumerate or optimize embeddings with forbidden short non-contractible cycles.

major comments (2)
  1. [§2] §2 (Definitions and equivalence): The claimed equivalence between the contraction-minimality definition and the 'every edge on a non-contractible k-cycle' definition is load-bearing for the subsequent charging argument. The manuscript does not explicitly address whether an edge contraction in a triangulation of genus g>1 can produce a digon or alter the homotopy class of the newly created (k-1)-curve, which would break the equivalence and invalidate the uniform application of the Euler-characteristic bound.
  2. [§4] §4 (Size bound derivation): The O(k²g) upper bound is obtained by charging triangles to non-contractible k-cycles after invoking the equivalence. If the equivalence fails for some contractions, the counting argument no longer applies uniformly across all edges, and the claimed linear dependence on g may not hold.
minor comments (2)
  1. [§5] The optimality construction achieving Θ(k²g) triangles is only sketched; a self-contained description of the family of examples would strengthen the claim.
  2. Notation for non-contractible curves and their homotopy classes is introduced without a short reminder of the standard surface fundamental-group facts used later; a one-sentence reference would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for raising these important points about the equivalence of definitions and its role in the size bound. We address each major comment below.

read point-by-point responses

  1. Referee: [§2] §2 (Definitions and equivalence): The claimed equivalence between the contraction-minimality definition and the 'every edge on a non-contractible k-cycle' definition is load-bearing for the subsequent charging argument. The manuscript does not explicitly address whether an edge contraction in a triangulation of genus g>1 can produce a digon or alter the homotopy class of the newly created (k-1)-curve, which would break the equivalence and invalidate the uniform application of the Euler-characteristic bound.

    Authors: The equivalence (Lemma 2.3) is proved topologically and does not depend on genus. If an edge lies on no shortest non-contractible k-cycle, contracting it yields a non-contractible curve of length at most k-1; the argument tracks homotopy classes directly via the universal cover and does not rely on the surface being a sphere. Triangulations contain no digons by definition, and contraction of an edge between distinct vertices cannot create a digon without already implying a shorter non-contractible cycle in the original complex, contradicting the girth hypothesis. We will insert a short paragraph in §2 explicitly verifying that the homotopy class of the resulting (k-1)-curve remains non-contractible precisely when the original edge was not on a k-cycle, covering g>1. revision: yes

  2. Referee: [§4] §4 (Size bound derivation): The O(k²g) upper bound is obtained by charging triangles to non-contractible k-cycles after invoking the equivalence. If the equivalence fails for some contractions, the counting argument no longer applies uniformly across all edges, and the claimed linear dependence on g may not hold.

    Authors: The charging scheme in §4 assigns each triangle to the non-contractible k-cycles through its edges; the equivalence guarantees every edge participates in at least one such cycle. The subsequent double-counting uses only the Euler characteristic χ=2-2g and the fact that each k-cycle uses O(k) triangles, yielding the O(k²g) bound independently of any further contraction details. Because the equivalence holds for all g (as clarified above), the linear dependence on g is preserved. We will add an explicit cross-reference from the charging argument back to Lemma 2.3. revision: partial

Circularity Check

0 steps flagged

No circularity: combinatorial bound derived from surface topology and Euler characteristic

full rationale

The paper states two equivalent definitions of k-irreducible triangulations and proves an O(k²g) upper bound on the number of triangles for genus-g surfaces. The derivation relies on standard topological facts about orientable surfaces, non-contractible curves, and Euler's formula rather than any fitted parameters, self-referential definitions, or load-bearing self-citations. The prior bound cited is from unrelated authors (Gao, Richter, Seymour) and is strictly weaker. No step reduces the claimed result to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard facts from combinatorial topology rather than introducing new fitted parameters or entities.

axioms (1)
  • standard math Standard properties of triangulations on orientable surfaces, including Euler characteristic and edge-contraction preserving triangulation structure
    Invoked implicitly when defining k-irreducible triangulations and deriving global size bounds from local girth conditions.

pith-pipeline@v0.9.0 · 5632 in / 1136 out tokens · 57575 ms · 2026-05-19T18:17:27.716801+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

44 extracted references · 44 canonical work pages

  1. [1]

    Untangling planar graphs and curves by staying positive

    Santiago Aranguri, Hsien-Chih Chang, and Dylan Fridman. Untangling planar graphs and curves by staying positive. InProceedings of the 33rd annual ACM-SIAM symposium on discrete algorithms, SODA 2022, Alexandria, VA, USA, both virtually and physically, January 9–12, 2022, pages 211–225. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM...

    work page doi:10.1137/1.9781611977073.11 2022

  2. [2]

    D. W. Barnette and Allan L. Edelson. All 2-manifolds have finitely many minimal trian- gulations.Isr. J. Math., 67(1):123–128, 1989.doi:10.1007/BF02764905

    work page doi:10.1007/bf02764905 1989

  3. [3]

    Generating the triangulations of the projective plane.J

    David Barnette. Generating the triangulations of the projective plane.J. Comb. Theory, Ser. B, 33:222–230, 1982.doi:10.1016/0095-8956(82)90041-7

    work page doi:10.1016/0095-8956(82)90041-7 1982

  4. [4]

    On the number of labeled graphs of bounded treewidth.Eur

    Julien Baste, Marc Noy, and Ignasi Sau. On the number of labeled graphs of bounded treewidth.Eur. J. Comb., 71:12–21, 2018.doi:10.1016/j.ejc.2018.02.030

    work page doi:10.1016/j.ejc.2018.02.030 2018

  5. [5]

    The geometry of Teichm¨ uller space via geodesic currents.Invent

    Francis Bonahon. The geometry of Teichm¨ uller space via geodesic currents.Invent. Math., 92(1):139–162, 1988.doi:10.1007/BF01393996

    work page doi:10.1007/bf01393996 1988

  6. [6]

    Irreducible tri- angulations of surfaces with boundary.Graphs Comb., 29(6):1675–1688, 2013.doi: 10.1007/s00373-012-1244-1

    Alexandre Boulch, ´Eric Colin de Verdi` ere, and Atsuhiro Nakamoto. Irreducible tri- angulations of surfaces with boundary.Graphs Comb., 29(6):1675–1688, 2013.doi: 10.1007/s00373-012-1244-1

    work page doi:10.1007/s00373-012-1244-1 2013

  7. [7]

    Local maxima of the systole function.J

    Maxime Fortier Bourque and Kasra Rafi. Local maxima of the systole function.J. Eur. Math. Soc. (JEMS), 24(2):623–668, 2022.doi:10.4171/JEMS/1113

    work page doi:10.4171/jems/1113 2022

  8. [8]

    Injectivity radius and low eigenvalues of hyperbolic manifolds.J

    Robert Brooks. Injectivity radius and low eigenvalues of hyperbolic manifolds.J. Reine Angew. Math., 390:117–129, 1988.doi:10.1515/crll.1988.390.117

    work page doi:10.1515/crll.1988.390.117 1988

  9. [9]

    Buser and P

    P. Buser and P. Sarnak. On the period matrix of a Riemann surface of large genus (with an appendix by J. H. Conway and N. J. A. Sloane).Invent. Math., 117(1):27–56, 1994. doi:10.1007/BF01232233

    work page doi:10.1007/bf01232233 1994

  10. [10]

    PhD thesis, University of Illinois at Urbana-Champaign, 2018

    Hsien-Chih Chang.Tightening curves and graphs on surfaces. PhD thesis, University of Illinois at Urbana-Champaign, 2018

    work page 2018

  11. [11]

    Lower bounds for electrical reduc- tion on surfaces

    Hsien-Chih Chang, Marcos Cossarini, and Jeff Erickson. Lower bounds for electrical reduc- tion on surfaces. In35th international symposium on computational geometry, SoCG 2019, Portland, Oregon, USA, June 18–21, 2019. Proceedings, page 16. Wadern: Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, 2019. Id/No 25.doi:10.4230/LIPIcs.SoCG.2019.25

    work page doi:10.4230/lipics.socg.2019.25 2019

  12. [12]

    Tightening curves on surfaces monotonically with applications.ACM Trans

    Hsien-Chih Chang and Arnaud de Mesmay. Tightening curves on surfaces monotonically with applications.ACM Trans. Algorithms, 18(4):32, 2022. Id/No 36.doi:10.1145/ 3558097

    work page 2022

  13. [13]

    Untangling planar curves.Discrete Comput

    Hsien-Chih Chang and Jeff Erickson. Untangling planar curves.Discrete Comput. Geom., 58(4):889–920, 2017.doi:10.1007/s00454-017-9907-6

    work page doi:10.1007/s00454-017-9907-6 2017

  14. [14]

    Index gap of the systole function, 2025

    Changjie Chen. Index gap of the systole function, 2025. URL:https://arxiv.org/abs/ 2309.05801,arXiv:2309.05801

    work page arXiv 2025

  15. [15]

    Computational topology of graphs on surfaces

    ´Eric Colin de Verdi` ere. Computational topology of graphs on surfaces. In Jacob E. Good- man, Joseph O’Rourke, and Csaba Toth, editors,Handbook of Discrete and Computational Geometry, chapter 23, pages 605–636. CRC Press LLC, third edition, 2018

    work page 2018

  16. [16]

    Discrete systolic inequal- ities and decompositions of triangulated surfaces.Discrete Comput

    ´Eric Colin de Verdi` ere, Alfredo Hubard, and Arnaud de Mesmay. Discrete systolic inequal- ities and decompositions of triangulated surfaces.Discrete Comput. Geom., 53(3):587–620, 2015.doi:10.1007/s00454-015-9679-9

    work page doi:10.1007/s00454-015-9679-9 2015

  17. [17]

    Discrete surfaces with length and area and minimal fillings of the circle,

    Marcos Cossarini. Discrete surfaces with length and area and minimal fillings of the circle,

    work page

  18. [18]

    URL:https://arxiv.org/abs/2009.02415,arXiv:2009.02415

    work page arXiv 2009

  19. [19]

    Minimal area of Finsler disks with minimizing geodesics.J

    Marcos Cossarini and St´ ephane Sabourau. Minimal area of Finsler disks with minimizing geodesics.J. Eur. Math. Soc. (JEMS), 26(3):985–1029, 2024.doi:10.4171/JEMS/1339. 17

    work page doi:10.4171/jems/1339 2024

  20. [20]

    Characterizing homotopy of systems of curves on a compact surface by crossing numbers.Linear Algebra Appl., 226-228:519–528, 1995

    Maurits de Graaf and Alexander Schrijver. Characterizing homotopy of systems of curves on a compact surface by crossing numbers.Linear Algebra Appl., 226-228:519–528, 1995. doi:10.1016/0024-3795(95)00161-J

    work page doi:10.1016/0024-3795(95)00161-j 1995

  21. [21]

    Decomposition of graphs on surfaces.J

    Maurits de Graaf and Alexander Schrijver. Decomposition of graphs on surfaces.J. Comb. Theory, Ser. B, 70(1):157–165, 1997.doi:10.1006/jctb.1997.1747

    work page doi:10.1006/jctb.1997.1747 1997

  22. [22]

    On the computation of schrijver’s kernels, 2025

    Vincent Delecroix, Oscar Fontaine, and Francis Lazarus. On the computation of schrijver’s kernels, 2025. To appear in the Proceedings of SODA 2026. URL:https://arxiv.org/ abs/2510.18597,arXiv:2510.18597

    work page arXiv 2025

  23. [23]

    Making multicurves cross minimally on surfaces

    Lo¨ ıc Dubois. Making multicurves cross minimally on surfaces. In Timothy M. Chan, Jo- hannes Fischer, John Iacono, and Grzegorz Herman, editors,32nd Annual European Sym- posium on Algorithms, ESA 2024, Royal Holloway, London, United Kingdom, September 2-4, 2024, volume 308 ofLIPIcs, pages 50:1–50:15. Schloss Dagstuhl - Leibniz-Zentrum f¨ ur Informatik, 2...

    work page doi:10.4230/lipics.esa.2024.50 2024

  24. [24]

    Ser.Princeton, NJ: Princeton University Press, 2011

    Benson Farb and Dan Margalit.A primer on mapping class groups, volume 49 ofPrinceton Math. Ser.Princeton, NJ: Princeton University Press, 2011

    work page 2011

  25. [25]

    Z. Gao, R. B. Richter, and P. D. Seymour. Irreducible triangulations of surfaces.J. Comb. Theory, Ser. B, 68(2):206–217, 1996.doi:10.1006/jctb.1996.0064

    work page doi:10.1006/jctb.1996.0064 1996

  26. [26]

    Filling Riemannian manifolds.J

    Mikhael Gromov. Filling Riemannian manifolds.J. Differ. Geom., 18:1–147, 1983.doi: 10.4310/jdg/1214509283

    work page doi:10.4310/jdg/1214509283 1983

  27. [27]

    Shortening curves on surfaces.Topology, 33(1):25–43, 1994

    Joel Hass and Peter Scott. Shortening curves on surfaces.Topology, 33(1):25–43, 1994

    work page 1994

  28. [28]

    Cambridge University Press, 2002

    Allen Hatcher.Algebraic Topology. Cambridge University Press, 2002. URL:https: //pi.math.cornell.edu/~hatcher/AT/ATpage.html

    work page 2002

  29. [29]

    Robert Hickingbotham, Freddie Illingworth, Bojan Mohar, and David R. Wood. Treewidth, circle graphs, and circular drawings.SIAM J. Discret. Math., 38(1):965–987, 2024.doi: 10.1137/22M1542854

    work page doi:10.1137/22m1542854 2024

  30. [30]

    Hutchinson

    Joan P. Hutchinson. On short noncontractible cycles in embedded graphs.SIAM J. Discrete Math., 1(2):185–192, 1988.doi:10.1137/0401020

    work page doi:10.1137/0401020 1988

  31. [31]

    Gwena¨ el Joret and David R. Wood. Irreducible triangulations are small.J. Comb. Theory, Ser. B, 100(5):446–455, 2010.doi:10.1016/j.jctb.2010.01.004

    work page doi:10.1016/j.jctb.2010.01.004 2010

  32. [32]

    [BB11] Samik Basu and Tevfik Bultan

    M. Juvan, A. Malniˇ c, and B. Mohar. Systems of curves on surfaces.J. Comb. Theory, Ser. B, 68(1):7–22, 1996.doi:10.1006/jctb.1996.0053

    work page doi:10.1006/jctb.1996.0053 1996

  33. [33]

    Katz.Systolic geometry and topology

    Mikhail G. Katz.Systolic geometry and topology. With an appendix by Jake P. Solomon, volume 137 ofMath. Surv. Monogr.Providence, RI: American Mathematical Society (AMS), 2007

    work page 2007

  34. [34]

    Katz and St´ ephane Sabourau

    Mikhail G. Katz and St´ ephane Sabourau. Systolically extremal nonpositively curved surfaces are flat with finitely many singularities.J. Topol. Anal., 13(2):319–347, 2021. doi:10.1142/S1793525320500144

    work page doi:10.1142/s1793525320500144 2021

  35. [35]

    Filling triangulated surfaces

    Ryan Kowalick, Jean-Fran¸ cois Lafont, and Barry Minemyer. Filling triangulated surfaces. Geom. Dedicata, 202:373–386, 2019.doi:10.1007/s10711-018-00419-9

    work page doi:10.1007/s10711-018-00419-9 2019

  36. [36]

    Malniˇ c and R

    A. Malniˇ c and R. Nedela.k-minimal triangulations of surfaces.Acta Math. Univ. Comen., New Ser., 64(1):57–76, 1995. URL:https://eudml.org/doc/119916. 18

    work page 1995

  37. [37]

    Massey.A basic course in algebraic topology, volume 127 ofGrad

    William S. Massey.A basic course in algebraic topology, volume 127 ofGrad. Texts Math. New York etc.: Springer-Verlag, 1991

    work page 1991

  38. [38]

    PhD thesis, Technis- che Universit¨ at Dresden, 2019

    Sebastian Melzer.k-irreducible triangulations of 2-manifolds. PhD thesis, Technis- che Universit¨ at Dresden, 2019. URL:https://nbn-resolving.org/urn:nbn:de:bsz: 14-qucosa2-356439

    work page 2019

  39. [39]

    Baltimore, MD: Johns Hopkins University Press, 2001

    Bojan Mohar and Carsten Thomassen.Graphs on surfaces. Baltimore, MD: Johns Hopkins University Press, 2001

    work page 2001

  40. [40]

    Note on irreducible triangulations of surfaces.J

    Atsuhiro Nakamoto and Katsuhiro Ota. Note on irreducible triangulations of surfaces.J. Graph Theory, 20(2):227–233, 1995.doi:10.1002/jgt.3190200211

    work page doi:10.1002/jgt.3190200211 1995

  41. [41]

    Schrijver

    A. Schrijver. Decomposition of graphs on surfaces and a homotopic circulation theorem. J. Comb. Theory, Ser. B, 51(2):161–210, 1991.doi:10.1016/0095-8956(91)90036-J

    work page doi:10.1016/0095-8956(91)90036-j 1991

  42. [42]

    Schrijver

    A. Schrijver. On the uniqueness of kernels.J. Comb. Theory, Ser. B, 55(1):146–160, 1992. doi:10.1016/0095-8956(92)90038-Y

    work page doi:10.1016/0095-8956(92)90038-y 1992

  43. [43]

    Polyeder und raumeinteilungen

    Ernst Steinitz. Polyeder und raumeinteilungen. InEncyclop¨ adie der mathematischen Wis- senschaften, volume Band 3 (Geometries), page 1–139. B.G. Teubner Verlag, 1922

    work page 1922

  44. [44]

    Generating irreducible triangulations of surfaces, 2006.arXiv:math/ 0606687

    Thom Sulanke. Generating irreducible triangulations of surfaces, 2006.arXiv:math/ 0606687. 19

    work page 2006