Email this article Counting lattice triangulations: Fredholm equations in combinatorics
- Authors: Orevkov S.Y.1
-
Affiliations:
- Steklov Mathematical Institute of Russian Academy of Sciences
- Issue: Vol 213, No 11 (2022)
- Pages: 50-78
- Section: Articles
- URL: https://journal-vniispk.ru/0368-8666/article/view/133493
- DOI: https://doi.org/10.4213/sm9727
- ID: 133493
Cite item
Open Access
Access granted
Subscription Access
Abstract
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.
About the authors
Stepan Yur'evich Orevkov
Steklov Mathematical Institute of Russian Academy of Sciences
Email: orevkov@math.ups-tlse.fr
Candidate of physico-mathematical sciences, Senior Researcher
References
- E. E. Anclin, “An upper bound for the number of planar lattice triangulations”, J. Combin. Theory Ser. A, 103:2 (2003), 383–386
- I. Fredholm, “Sur une classe d'equations fonctionnelles”, Acta Math., 27:1 (1903), 365–390
- I. M. Gelfand, M. M. Kapranov, A. V. Zelevinsky, Discriminants, resultants, and multidimensional determinants, Math. Theory Appl., Birkhäuser Boston, Inc., 1994, x+523 pp.
- V. Kaibel, 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
- Л. В. Канторович, В. И. Крылов, Приближенные методы высшего анализа, 5-е изд., испр., Физматгиз, М.–Л., 1962, 708 с.
- Б. В. Хведелидзе, “Фредгольма уравнение”, Математическая энциклопедия, ред. И. М. Виноградов, Сов. энциклопедия, М., 1977
- J. Matoušek, P. Valtr, E. Welzl, On two encodings of lattice triangulations, manuscript, 2006
- S. Yu. Orevkov, “Asymptotic number of triangulations with vertices in $mathbf Z^2$”, J. Combin. Theory Ser. A, 86:1 (1999), 200–203
- С. Ю. Оревков, В. М. Харламов, “Порядок роста числа классов вещественных плоских алгебраических кривых при возрастании степени”, Теория представлений, динамические системы, комбинаторные и алгоритмические методы. V, Зап. науч. сем. ПОМИ, 266, ПОМИ, СПб., 2000, 218–233
- M. Sharir, A. Sheffer, “Counting triangulations of planar point sets”, Electron. J. Combin., 18:1 (2011), 70, 74 pp.
- 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
- E. Welzl, “The number of triangulations on planar point sets”, Graph drawing, Lecture Notes in Comput. Sci., 4372, Springer, Berlin, 2007, 1–4
- E. Welzl, J. Matušek, P. Valtr, Lattice triangulations, Talk in Freie Univ. (Berlin, 2006)
Supplementary files
