Geodesic
Counting lattice triangulations: Fredholm equations in combinatorics
Sbornik. Mathematics, Tome 213 (2022) no. 11, pp. 1530-1558 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Let $f(m,n)$ be the number of primitive lattice triangulations of an $m\times n$ rectangle. We compute the limits $\lim_n f(m,n)^{1/n}$ for $m=2,3$. For $m=2$ we obtain the exact value of the limit, which is $(611+\sqrt{73})/36$. For $m=3$ we express the limit in terms of a certain Fredholm integral equation for generating functions. This provides a polynomial-time algorithm (with respect to the number of computed digits) for the computation of the limit with any prescribed precision. Bibliography: 13 titles.
Keywords: asymptotic, primitive triangulation, Fredholm's integral equation. 
@article{SM_2022_213_11_a4,
     author = {S. Yu. Orevkov},
     title = {Counting lattice triangulations: {Fredholm} equations in combinatorics},
     journal = {Sbornik. Mathematics},
     pages = {1530--1558},
     year = {2022},
     volume = {213},
     number = {11},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_2022_213_11_a4/}
}
TY  - JOUR
AU  - S. Yu. Orevkov
TI  - Counting lattice triangulations: Fredholm equations in combinatorics
JO  - Sbornik. Mathematics
PY  - 2022
SP  - 1530
EP  - 1558
VL  - 213
IS  - 11
UR  - http://geodesic.mathdoc.fr/item/SM_2022_213_11_a4/
LA  - en
ID  - SM_2022_213_11_a4
ER  - 
%0 Journal Article
%A S. Yu. Orevkov
%T Counting lattice triangulations: Fredholm equations in combinatorics
%J Sbornik. Mathematics
%D 2022
%P 1530-1558
%V 213
%N 11
%U http://geodesic.mathdoc.fr/item/SM_2022_213_11_a4/
%G en
%F SM_2022_213_11_a4
S. Yu. Orevkov. Counting lattice triangulations: Fredholm equations in combinatorics. Sbornik. Mathematics, Tome 213 (2022) no. 11, pp. 1530-1558. http://geodesic.mathdoc.fr/item/SM_2022_213_11_a4/

[1] E. E. Anclin, “An upper bound for the number of planar lattice triangulations”, J. Combin. Theory Ser. A, 103:2 (2003), 383–386 | DOI | MR | Zbl

[2] I. Fredholm, “Sur une classe d'équations fonctionnelles”, Acta Math., 27:1 (1903), 365–390 | DOI | MR | Zbl

[3] I. M. Gelfand, M. M. Kapranov and A. V. Zelevinsky, Discriminants, resultants, and multidimensional determinants, Math. Theory Appl., Birkhäuser Boston, Inc., 1994, x+523 pp. | DOI | MR | Zbl

[4] V. Kaibel and G. M. Ziegler, “Counting lattice triangulations”, Surveys in combinatorics 2003 (Univ. of Wales, Bangor, UK 2003), London Math. Soc. Lecture Note Ser., 307, Cambridge Univ. Press, Cambridge, 2003, 277–307 | DOI | MR | Zbl

[5] L. V. Kantorovich and V. I. Krylov, Approximate methods of higher analysis, 5th corr. ed., Fizmatgiz, Moscow–Leningrad, 1962, 708 pp. ; English transl. of 3rd ed., Interscience Publishers, Inc., New York; P. Noordhoff Ltd., Groningen, 1958, xv+681 pp. | MR | Zbl | MR | Zbl

[6] B. V. Khvedelidze, “Fredholm equation”, Matematicheskaya Entsiklopediya, ed. I. M. Vinogradov, Sov. Entsiklopediya, Moscow, 1977; English transl., Fredholm equation, Encyclopedia of Mathematics http://encyclopediaofmath.org/index.php?title=Fredholm_equation&oldid=46977

[7] J. Matoušek, P. Valtr and E. Welzl, On two encodings of lattice triangulations, Manuscript, 2006

[8] S. Yu. Orevkov, “Asymptotic number of triangulations with vertices in $\mathbf Z^2$”, J. Combin. Theory Ser. A, 86:1 (1999), 200–203 | DOI | MR | Zbl

[9] S. Yu. Orevkov and V. M. Kharlamov, “Asymptotic growth of the number of classes of real plane algebraic curves as the degree grows”, Representation theory, dynamical systems, combinatorial and algorithmic methods. Part V, Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI), 266, St. Petersburg Department of Steklov Mathematical Institute, St. Petersburg, 2000, 218–233 ; English transl. in J. Math. Sci. (N.Y.), 113:5 (2003), 666–674 | MR | Zbl | DOI

[10] M. Sharir and A. Sheffer, “Counting triangulations of planar point sets”, Electron. J. Combin., 18:1 (2011), 70, 74 pp. | DOI | MR | Zbl

[11] J. D. Tamarkin, “On Fredholm's integral equations, whose kernels are analytic in a parameter”, Ann. of Math. (2), 28:1–2 (1926–1927), 127–152 | DOI | MR | Zbl

[12] E. Welzl, “The number of triangulations on planar point sets”, Graph drawing, Lecture Notes in Comput. Sci., 4372, Springer, Berlin, 2007, 1–4 | DOI | MR | Zbl

[13] E. Welzl, J. Matušek and P. Valtr, Lattice triangulations, Talk in Freie Univ. (Berlin 2006)