Отправить статью по E-mail Перечисление целочисленных триангуляций: уравнения Фредгольма в комбинаторике
- Авторы: Оревков С.Ю.1
-
Учреждения:
- Математический институт им. В.А. Стеклова Российской академии наук
- Выпуск: Том 213, № 11 (2022)
- Страницы: 50-78
- Раздел: Статьи
- URL: https://journal-vniispk.ru/0368-8666/article/view/133493
- DOI: https://doi.org/10.4213/sm9727
- ID: 133493
Цитировать
Открытый доступ
Доступ предоставлен
Только для подписчиков
Аннотация
Пусть $f(m,n)$ – число примитивных целочисленных триангуляций прямоугольника $m\times n$. Вычислены пределы $\lim_n f(m,n)^{1/n}$ при $m=2,3$. При $m=2$ найдено точное значение предела, равное $(611+\sqrt{73})/36$. При $m=3$ предел выражен в терминах интегрального уравнения Фредгольма на некоторые производящие функции. Это дает алгоритм, вычисляющий значение предела с любой точностью за полиномиальное время (полиномиальное относительно количества найденных цифр).Библиография: 13 названий.
Ключевые слова
Об авторах
Степан Юрьевич Оревков
Математический институт им. В.А. Стеклова Российской академии наук
Email: orevkov@math.ups-tlse.fr
кандидат физико-математических наук, старший научный сотрудник
Список литературы
- 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)
Дополнительные файлы
