Lattice points of flow polytopes related to caracol graphs

Hua Xin; Hua Xin

doi:10.3934/era.2025272

Electronic Research Archive

2025, Volume 33, Issue 10: 6141-6175. doi: 10.3934/era.2025272

Previous Article Next Article

Research article

Lattice points of flow polytopes related to caracol graphs

Hua Xin ^,

Institute for Advanced Study in Mathematics, Harbin Institute of Technology, Harbin 150001, China

Received: 30 May 2025 Revised: 08 September 2025 Accepted: 10 October 2025 Published: 20 October 2025

Flow polytopes are fundamental objects in algebraic combinatorics. In this paper, we study the enumeration of lattice points in flow polytopes associated with $ (a_1, a_2) $-caracol graphs on $ n + 2 $ vertices. Our main result establishes a closed-form expression for the number of lattice points by constructing an explicit combinatorial bijection between Dyck paths and the integer lattice points of the two-parameter family of polytopes $ (a_1, a_2) $-Car $ _{n+1} $, using pseudo-ladder diagrams together with vector partition techniques. When $ a_{2} = 1 $, the lattice point sequence of caracol polytopes coincides with the OEIS sequence A126216 (The On-Line Encyclopedia of Integer Sequences), which enumerates Schröder paths of semilength $ n $ with exactly $ k $ peaks. Furthermore, we establish a bijection between Schröder paths and the integer lattice points of the two-parameter family of polytopes $ (a_1, a_2) $-Car $ _{n+1} $. All bijections are implemented as explicit algorithms in Python, with the complete source code provided in the appendix to ensure reproducibility.
- flow polytopes,
- caracol graphs,
- lattice points,
- lattice paths,
- Kostant partition functions
Citation: Hua Xin. Lattice points of flow polytopes related to caracol graphs[J]. Electronic Research Archive, 2025, 33(10): 6141-6175. doi: 10.3934/era.2025272

Related Papers:

Abstract

Flow polytopes are fundamental objects in algebraic combinatorics. In this paper, we study the enumeration of lattice points in flow polytopes associated with $ (a_1, a_2) $-caracol graphs on $ n + 2 $ vertices. Our main result establishes a closed-form expression for the number of lattice points by constructing an explicit combinatorial bijection between Dyck paths and the integer lattice points of the two-parameter family of polytopes $ (a_1, a_2) $-Car $ _{n+1} $, using pseudo-ladder diagrams together with vector partition techniques. When $ a_{2} = 1 $, the lattice point sequence of caracol polytopes coincides with the OEIS sequence A126216 (The On-Line Encyclopedia of Integer Sequences), which enumerates Schröder paths of semilength $ n $ with exactly $ k $ peaks. Furthermore, we establish a bijection between Schröder paths and the integer lattice points of the two-parameter family of polytopes $ (a_1, a_2) $-Car $ _{n+1} $. All bijections are implemented as explicit algorithms in Python, with the complete source code provided in the appendix to ensure reproducibility.

References

[1]	A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Vol. A. Paths, Flows, Matchings. Chapters 1–38, Algorithms Combin., 24A, Springer-Verlag, Berlin, (2003), Chapter 13,198–216.
[2]	J. E. Humphreys, Introduction to Lie Algebras and Representation Theory, Second printing, revised, Graduate Texts in Mathematics, 9, Springer-Verlag, New York–Berlin, (1978), xii+171 pp.
[3]	K. Mészáros, A. H. Morales, B. Rhoades, The polytope of Tesler matrices, Selecta Math. (N.S.), 23 (2017), 425–454. https://doi.org/10.1007/s00029-016-0241-2 doi: 10.1007/s00029-016-0241-2
[4]	L. Hille, Quivers, cones and polytopes, Linear Algebra Appl., 365 (2003), 215–237. https://doi.org/10.1016/S0024-3795(02)00406-8
[5]	W. Baldoni, M. Vergne, Kostant partition functions and flow polytopes, Transform. Groups, 13 (2008), 447–469. https://doi.org/10.1007/s00031-008-9019-8 doi: 10.1007/s00031-008-9019-8
[6]	R. P. Stanley, A. Postnikov, Acyclic flow polytopes and Kostant's partition function, in Conference Transparencies, 2000.
[7]	M. Beck, S. Robins, Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra, Undergrad. Texts Math., Springer, New York, (2007), xviii+226 pp.
[8]	R. Simion, Convex polytopes and enumeration, Adv. Appl. Math., 18 (1997), 149–180. https://doi.org/10.1006/aama.1996.0505 doi: 10.1006/aama.1996.0505
[9]	B. V. Lidskii, The Kostant function of the system of roots $ A_n $, Funktsional. Anal. i Prilozhen., 18 (1984), 76–77. https://doi.org/10.1007/BF01076370 doi: 10.1007/BF01076370
[10]	A. Postnikov, Flows in Networks, PhD thesis, Massachusetts Institute of Technology, 1997.
[11]	D. Zeilberger, Proof of the alternating sign matrix conjecture, Electron. J. Combin., 3 (1996), 84. https://doi.org/10.37236/1271 doi: 10.37236/1271
[12]	K. Mészáros, A. H. Morales, Volumes and Ehrhart polynomials of flow polytopes, Math. Z., 293 (2019), 1369–1401. https://doi.org/10.1007/s00209-019-02283-z doi: 10.1007/s00209-019-02283-z
[13]	J. B. Liu, L. Guan, J. Cao, L. Chen, Coherence analysis for a class of polygon networks with the noise disturbance, IEEE Trans. Syst. Man Cybern. Syst., 55 (2025), 4718–4727. https://doi.org/10.1109/TSMC.2025.3559326 doi: 10.1109/TSMC.2025.3559326
[14]	C. Benedetti, R. S. González D'León, C. R. H. Hanusa, P. E. Harris, A. Khare, A. H. Morales, et al., A combinatorial model for computing volumes of flow polytopes, Trans. Amer. Math. Soc., 372 (2019), 3369–3404. https://doi.org/10.1090/tran/7743 doi: 10.1090/tran/7743
[15]	K. Mészáros, A. H. Morales, Flow polytopes of signed graphs and the Kostant partition function, Int. Math. Res. Not., 3 (2015), 830–871. https://doi.org/10.1093/imrn/rnt212 doi: 10.1093/imrn/rnt212
[16]	J. Jang, J. S. Kim, Volumes of flow polytopes related to caracol graphs, Electron. J. Combin., 27 (2020), 21. https://doi.org/10.37236/9187 doi: 10.37236/9187
[17]	I. Fischer, Counting integer points in polytopes associated with directed graphs, Adv. Appl. Math., 79 (2016), 125–153. https://doi.org/10.1016/j.aam.2016.04.008 doi: 10.1016/j.aam.2016.04.008
[18]	K. Mészáros, A. H. Morales, J. Striker, On flow polytopes, order polytopes, and certain faces of the alternating sign matrix polytope, Discrete Comput. Geom., 62 (2019), 128–163. https://doi.org/10.1007/s00454-019-00073-2 doi: 10.1007/s00454-019-00073-2
[19]	C. S. Chan, D. P. Robbins, D. S. Yuen, On the volume of a certain polytope, Experiment. Math., 9 (2000), 91–99. http://projecteuclid.org/euclid.em/1046889594
[20]	R. P. Stanley, A survey of alternating permutations, in Combinatorics and Graphs, (2010), 165–196. https://doi.org/10.1090/conm/531/10466
[21]	R. P. Stanley, J. Pitman, A polytope related to empirical distributions, plane trees, parking functions, and the associahedron, Discrete Comput. Geom., 27 (2002), 603–634. https://doi.org/10.1007/s00454-002-2776-6 doi: 10.1007/s00454-002-2776-6
[22]	N. J. A. Sloane, On-line Encyclopedia of Integer Sequences (OEIS), 2018. Available from: https://oeis.org.
[23]	E. Barcucci, A. Bernini, R. Pinzani, Exhaustive generation of some lattice paths and their prefixes, Theoret. Comput. Sci., 878/879 (2021), 47–52. https://doi.org/10.1016/j.tcs.2020.12.013 doi: 10.1016/j.tcs.2020.12.013
[24]	R. R. X. Du, Y. Nie, X. Sun, Enumerations of humps and peaks in $(k, a)$-paths and $(n, m)$-Dyck paths via bijective proofs, Discrete Appl. Math., 190/191 (2015), 42–49. https://doi.org/10.1016/j.dam.2015.04.005 doi: 10.1016/j.dam.2015.04.005
[25]	R. Cori, A. Frosini, G. Palma, E. Pergola, S. Rinaldi, On doubly symmetric Dyck words, Theor. Comput. Sci., 896 (2021), 79–97. https://doi.org/10.1016/j.tcs.2021.10.006 doi: 10.1016/j.tcs.2021.10.006
[26]	T. Mansour, E. Y. P. Deng, R. R. X. Du, Dyck paths and restricted permutations. Discrete Appl. Math., 154 (2006), 1593–1605. https://doi.org/10.1016/j.dam.2006.02.004 doi: 10.1016/j.dam.2006.02.004
[27]	R. A. Sulanke, Three dimensional Narayana and Schröder numbers, Theor. Comput. Sci., 346 (2005), 455–468. https://doi.org/10.1016/j.tcs.2005.08.014 doi: 10.1016/j.tcs.2005.08.014
[28]	L. Yang, S. L. Yang, A Chung-Feller property for the generalized Schröder paths, Discrete Math., 343 (2020), 111826. https://doi.org/10.1016/j.disc.2020.111826 doi: 10.1016/j.disc.2020.111826
[29]	L. Yang, Y. Y. Zhang, S. L. Yang, The halves of Delannoy matrix and Chung-Feller properties of the m-Schröder paths, Linear Algebra Appl., 685 (2024), 138–161. https://doi.org/10.1016/j.laa.2023.12.021 doi: 10.1016/j.laa.2023.12.021
[30]	K. H. Zhang, T. Wang, W. H. Luo, W. Q. Ren, B. Stenger, W. Liu, et al., Mc-blur: A comprehensive benchmark for image deblurring, IEEE Trans. Circuits Syst. Video Technol., 34 (2024), 3755–3767. https://doi.org/10.1109/TCSVT.2023.3319330 doi: 10.1109/TCSVT.2023.3319330
[31]	K. H. Zhang, W. H. Luo, Y. R. Zhong, L. Ma, W. Liu, H. D. Li, Adversarial spatio-temporal learning for video deblurring, IEEE Trans. Image Process., 28 (2018), 291–301. https://doi.org/10.1109/TIP.2018.2867733 doi: 10.1109/TIP.2018.2867733
[32]	K. H. Zhang, W. Q. Ren, W. H. Luo, W. S. Lai, B. Stenger, M. H. Yang, et al., Deep image deblurring: A survey, Int. J. Comput. Vis., 130 (2022), 2103–2130. https://doi.org/10.1007/s11263-022-01633-5 doi: 10.1007/s11263-022-01633-5

Reader Comments

Your name:*

Email:*
© 2025 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)