Lattice points of flow polytopes related to caracol graphs

i

This article has been updated. A Correction to this article was published on .

i

The Original Article was published on

i

The Original Article was published on

i

This article has been updated

i

This article was retracted on

i

This article has been updated

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₁,a₂)-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 (a1,a2)-$\mathrm{Car}_{n+1}$, using pseudo-ladder diagrams together with vector partition techniques. When a₂ = 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 (a1,a2)-$\mathrm{Car}_{n+1}$. All bijections are implemented as explicit algorithms in Python, with the complete source code provided in the appendix to ensure reproducibility.

Keywords

flow polytopes / caracol graphs / lattice points / lattice paths / Kostant partition functions

CHANGE HISTORY

A Correction to this paper has been published:
https://doi.org

The Retraction Note was updated to reflect reception of statements of disagreement from all authors.

This article has been retracted.Please see the Retraction Notice for more detail:
https://doi.org

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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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