Семантические пределы плотных комбинаторных объектов

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

Теория пределов дискретных комбинаторных объектов успешно развивается в течение последнего десятилетия. Синтаксический, алгебраический подход к предмету широко известен как “алгебры флагов”, тогда как семантический, геометрический подход часто именуется “пределами графов”. Язык теории пределов графов в целом более наглядный и выразительный, но той ценой, что он лучше подходит для простых графов, чем для более общих комбинаторных объектов. Сообразно этому, из литературы известны несколько попыток (разной степени общности) определить предельные объекты для более сложных комбинаторных структур.Настоящая статья – еще одна попытка получить рабочую общую теорию плотных предельных объектов. В отличие от предыдущих усилий в этом направлении (за важным исключением работы А. Ароскара и Дж. Каммингса 2014 г.), наши построения основанына тех же понятиях логики первого порядка и теории моделей, что используются в теории алгебр флагов.Показано, что наши определения естественным образом охватывают многие ранее рассматривавшиеся случаи (такие как графоны, гиперграфоны,направленные графоны, пермутоны, посетоны, раскрашенные графы и пр.),а фундаментальные свойства существования и единственности распространяютсяна этот более общий случай. Также приведено наглядное общее доказательствонепрерывного варианта индуцированной леммы об удалении,основанное на теореме компактности для логики высказываний.Особо выделяется понятие открытой интерпретации, часто позволяющее переноситьметоды и результаты с одной ситуации на другую. И в этом случае показано,что некоторые ранее известные рассуждения можно довольно естественно выразитьна таком языке.Библиография: 68 названий.

Об авторах

Леонардо Нагами Корельяно

University of Chicago

Email: lenacore@uchicago.edu

Александр Александрович Разборов

University of Chicago; Математический институт им. В.А. Стеклова Российской академии наук; Toyota Technological Institute at Chicago

Email: razborov@mi-ras.ru
доктор физико-математических наук, без звания

Список литературы

  1. N. Ackerman, C. Freer, R. Patel, “Invariant measures concentrated on countable structures”, Forum Math. Sigma, 4 (2016), e17, 59 pp.
  2. D. J. Aldous, “Representations for partially exchangeable arrays of random variables”, J. Multivariate Anal., 11:4 (1981), 581–598
  3. D. J. Aldous, “Exchangeability and related topics”, Ecole d'ete de probabilites de Saint-Flour XIII – 1983, Lecture Notes in Math., 1117, Springer, Berlin, 1985, 1–198
  4. N. Alon, J. H. Spencer, The probabilistic method, Wiley-Intersci. Ser. Discrete Math. Optim., 3rd ed., John Wiley & Sons, Inc., Hoboken, NJ, 2008, xviii+352 pp.
  5. A. Aroskar, J. Cummings, “Limits, regularity and removal for finite structures”, 2014, 26 pp.
  6. T. Austin, “On exchangeable random variables and the statistics of large graphs and hypergraphs”, Probab. Surv., 5 (2008), 80–145
  7. T. Austin, T. Tao, “Testability and repair of hereditary hypergraph properties”, Random Structures Algorithms, 36:4 (2010), 373–463
  8. R. Baber, Some results in extremal combinatorics, Thesis (Ph.D.), Univ. of London, Univ. College London (UK), 2011, 149 pp.
  9. J. Balogh, P. Hu, B. Lidicky, H. Liu, “Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube”, European J. Combin., 35 (2014), 75–85
  10. J. Balogh, P. Hu, B. Lidicky, F. Pfender, J. Volec, M. Young, “Rainbow triangles in three-colored graphs”, J. Combin. Theory Ser. B, 126 (2017), 83–113
  11. Дж. Барвайс (ред.), Справочная книга по математической логике, Ч. I–IV, Наука, М., 1982, 1983, 392 с., 375 с., 360 с., 391 с.
  12. В. И. Богачев, Основы теории меры, т. 1, 2, 2-е изд., НИЦ “Регулярная и хаотическая динамика”, М.–Ижевск, 2006, 583 с., 679 с.
  13. B. Bollobas, O. Riordan, “Metrics for sparse graphs”, Surveys in combinatorics 2009, London Math. Soc. Lecture Note Ser., 365, Cambridge Univ. Press, Cambridge, 2009, 211–287
  14. B. Bollobas, O. Riordan, “Sparse graphs: metrics and random models”, Random Structures Algorithms, 39:1 (2011), 1–38
  15. C. Borgs, J. T. Chayes, H. Cohn, Y. Zhao, “An {$L^p$} theory of sparse graph convergence. I. Limits, sparse random graph models, and power law distributions”, Trans. Amer. Math. Soc., 372:5 (2019), 3019–3062
  16. C. Borgs, J. T. Chayes, H. Cohn, Y. Zhao, “An $L^p$ theory of sparse graph convergence. II. LD convergence, quotients and right convergence”, Ann. Probab., 46:1 (2018), 337–396
  17. C. Borgs, J. T. Chayes, L. Lovasz, V. Sos, K. Vesztergombi, “Convergent sequences of dense graphs. I. Subgraph frequencies, metric properties and testing”, Adv. Math., 219:6 (2008), 1801–1851
  18. P. Brass, G. Karolyi, P. Valtr, “A Turan-type extremal theory of convex geometric graphs”, Discrete and computational geometry, Algorithms Combin., 25, Springer, Berlin, 2003, 275–300
  19. L. Caccetta, R. Häggkvist, “On minimal digraphs with given girth”, Proceedings of the 9th southeastern conference on combinatorics, graph theory, and computing (Florida Atlantic Univ., Boca Raton, FL, 1978), Congress. Numer., 21, Utilitas Math., Winnipeg, MB, 1978, 181–187
  20. P. J. Cameron, “The random graph”, The mathematics of Paul Erdős, v. II, Algorithms Combin., 14, Springer, Berlin, 1997, 333–351
  21. Г. Кейслер, Ч. Ч. Чэн, Теория моделей, Мир, М., 1977, 616 с.
  22. S. Chatterjee, A. Dembo, “Nonlinear large deviations”, Adv. Math., 299 (2016), 396–450
  23. F. R. K. Chung, R. L. Graham, “Quasi-random tournaments”, J. Graph Theory, 15:2 (1991), 173–198
  24. F. R. K. Chung, R. L. Graham, R. M. Wilson, “Quasi-random graphs”, Combinatorica, 9 (1989), 345–362
  25. P. Diaconis, D. Freedman, “On the statistics of vision: the Julesz conjecture”, J. Math. Psych., 24:2 (1981), 112–138
  26. P. Diaconis, D. Freedman, “Partial exchangeability and sufficiency”, Statistics: applications and new directions (Calcutta, 1981), Indian Statist. Inst., Calcutta, 1984, 205–236
  27. P. Diaconis, S. Holmes, S. Janson, “Threshold graph limits and random threshold graphs”, Internet Math., 5:3 (2008), 267–320
  28. P. Diaconis, S. Holmes, S. Janson, “Interval graph limits”, Ann. Comb., 17:1 (2013), 27–52
  29. P. Diaconis, S. Janson, “Graph limits and exchangeable random graphs”, Rend. Mat. Appl. (7), 28:1 (2008), 33–61
  30. G. Elek, B. Szegedy, “A measure-theoretic approach to the theory of dense hypergraphs”, Adv. Math., 231:3-4 (2012), 1731–1772
  31. Д. Г. Фон-Дер-Флаас, “Об одном способе построения $(3,4)$-графов”, Матем. заметки, 44:4 (1988), 546–550
  32. W. T. Gowers, “Quasirandomness, counting and regularity for 3-uniform hypergraphs”, Combin. Probab. Comput., 15:1-2 (2006), 143–184
  33. H. Hatami, P. Hatami, J. Hirst, “Limits of boolean functions on $mathbb F_p^n$”, Electron. J. Combin., 21:4 (2014), P4.2, 15 pp.
  34. H. Hatami, S. Norine, “Undecidability of linear inequalities in graph homomorphism densities”, J. Amer. Math. Soc., 24:2 (2011), 547–565
  35. J. Hladky, A. Mathe, V. Patel, O. Pikhurko, “Poset limits can be totally ordered”, Trans. Amer. Math. Soc., 367:6 (2015), 4319–4337
  36. D. N. Hoover, Relations on probability spaces and arrays of random variables, Preprint, Institute for Advanced Study, Princeton, NJ, 1979, 63 pp.
  37. C. Hoppen, Y. Kohayakawa, C. G. Moreira, B. Rath, R. Menezes Sampaio, “Limits of permutation sequences”, J. Combin. Theory Ser. B, 103:1 (2013), 93–113
  38. S. Janson, “Poset limits and exchangeable random posets”, Combinatorica, 31:5 (2011), 529–563
  39. S. Janson, “Quasi-random graphs and graph limits”, European J. Combin., 32:7 (2011), 1054–1083
  40. G. Japaridze, D. de Jongh, “The logic of provability”, Handbook of proof theory, Stud. Logic Found. Math., 137, North-Holland, Amsterdam, 1998, 475–546
  41. O. Kallenberg, “Symmetries on random arrays and set-indexed processes”, J. Theoret. Probab., 5:4 (1992), 727–765
  42. O. Kallenberg, Probabilistic symmetries and invariance principles, Probab. Appl. (N. Y.), Springer, New York, 2005, xii+510 pp.
  43. P. Keevash, “Hypergraph Turan problems”, Surveys in combinatorics 2011 (Exeter, UK), London Math. Soc. Lecture Note Ser., 392, Cambridge Univ. Press, Cambridge, 2011, 83–139
  44. L. Lovasz, Large networks and graph limits, Amer. Math. Soc. Colloq. Publ., 60, Amer. Math. Soc., Providence, RI, 2012, xiv+475 pp.
  45. L. Lovasz, B. Szegedy, “Limits of dense graph sequences”, J. Combin. Theory Ser. B, 96:6 (2006), 933–957
  46. L. Lovasz, B. Szegedy, “Finitely forcible graphons”, J. Combin. Theory Ser. B, 101:5 (2011), 269–301
  47. M. Malliaris, S. Shelah, “Regularity lemmas for stable graphs”, Trans. Amer. Math. Soc., 366:3 (2014), 1551–1585
  48. D. Mubayi, A. Razborov, Polynomial to exponential transition in Ramsey theory, 2020 (v1 – 2019), 27 pp.
  49. J. C. Oxtoby, Measure and category, A survey of the analogies between topological and measure spaces, Grad. Texts in Math., 2, 2nd ed., Springer-Verlag, New York–Berlin, 1980, x+106 pp.
  50. J. Pach, G. Tardos, “Forbidden paths and cycles in ordered graphs and matrices”, Israel J. Math., 155 (2006), 359–380
  51. F. Petrov, General removal lemma, 2013, 5 pp.
  52. F. Petrov, A. Vershik, “Uncountable graphs and invariant measures on the set of universal countable graphs”, Random Structures Algorithms, 37:3 (2010), 389–406
  53. М. О. Рабин, “Разрешимые теории”, Справочная книга по математической логике, Ч. III, Наука, М., 1982, 77–111
  54. A. A. Razborov, “Flag algebras”, J. Symbolic Logic, 72:4 (2007), 1239–1282
  55. А. А. Разборов, “Об интерпретации Фон-Дер-Флаасса экстремальных примеров для $(3,4)$-проблемы Турана”, Алгоритмические вопросы алгебры и логики, Сборник статей. К 80-летию со дня рождения академика Сергея Ивановича Адяна, Тр. МИАН, 274, МАИК “Наука/Интерпериодика”, М., 2011, 269–290
  56. A. A. Razborov, “Flag algebras: an interim report”, The mathematics of Paul Erdös II, 2nd ed., Springer, New York, 2013, 207–232
  57. V. Rödl, M. Schacht, “Generalizations of the removal lemma”, Combinatorica, 29:4 (2009), 467–501
  58. W. Rudin, Functional analysis, Internat. Ser. Pure Appl. Math., 2nd ed., McGraw-Hill, Inc., 1991, xviii+424 pp.
  59. A. Saad, J. Wolf, “Ramsey multiplicity of linear patterns in certain finite abelian groups”, Q. J. Math., 68:1 (2017), 125–140
  60. Дж. Шенфилд, Математическая логика, Наука, М., 1975
  61. E. Spiegel, Ch. J. O'Donnell, Incidence algebras, Monogr. Textbooks Pure Appl. Math., 206, Marcel Dekker, Inc., New York, 1997, x+335 pp.
  62. B. Szegedy, Gowers norms, regularization and limits of functions on abelian groups, 2010, 35 pp.
  63. G. Tardos, “Extremal theory of ordered graphs”, Proceedings of the international congress of mathematicians (Rio de Janeiro, 2018), v. 4, World Sci. Publ., Hackensack, NJ, 2018, 3235–3243
  64. A. Tarski, A. Mostowski, R. M. Robinson, Undecidable theories, Stud. Logic Found. Math., North-Holland Publishing Co., Amsterdam, 1953, xi+98 pp.
  65. A. Thomason, “Pseudo-random graphs”, Random graphs' 85 (Poznan, 1985), North-Holland Math. Stud., 144, Ann. Discrete Math., 33, North-Holland, Amsterdam, 1987, 307–331
  66. P. Turan, “Egy grafelmeleti szelsöertek feladatrol”, Mat. Fiz. Lapok, 48 (1941), 436–452
  67. А. М. Вершик, “Классификация измеримых функций нескольких аргументов и инвариантно распределенные случайные матрицы”, Функц. анализ и его прил., 36:2 (2002), 12–27
  68. Yu. Yoshida, “Gowers norm, function limits, and parameter estimation”, Proceedings of the 27th annual ACM–SIAM symposium on discrete algorithms, ACM, New York, 2016, 1391–1406

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Корельяно Л.Н., Разборов А.А., 2020

Согласие на обработку персональных данных

 

Используя сайт https://journals.rcsi.science, я (далее – «Пользователь» или «Субъект персональных данных») даю согласие на обработку персональных данных на этом сайте (текст Согласия) и на обработку персональных данных с помощью сервиса «Яндекс.Метрика» (текст Согласия).