Semantic limits of dense combinatorial objects

封面

如何引用文章

全文:

开放存取 开放存取
受限制的访问 ##reader.subscriptionAccessGranted##
受限制的访问 订阅存取

详细

The theory of limits of discrete combinatorial objects has been thriving for the last decade or so. The syntactic, algebraic approach to the subject is popularly known as ‘flag algebras’, while the semantic, geometric approach is often associated with the name ‘graph limits’. The language of graph limits is generally more intuitive and expressible, but a price that one has to pay for it is that it is better suited for the case of ordinary graphs than for more general combinatorial objects. Accordingly, there have been several attempts in the literature, of varying degree of generality, to define limit objects for more complicated combinatorial structures. This paper is another attempt at a workable general theory of dense limit objects. Unlike previous efforts in this direction (with the notable exception of [5] by Aroskar and Cummings), our account is based on the same concepts from first-order logic and model theory as in the theory of flag algebras. It is shown how our definitions naturally encompass a host of previously considered cases (graphons, hypergraphons, digraphons, permutons, posetons, coloured graphs, and so on), and the fundamental properties of existence and uniqueness are extended to this more general case. Also given is an intuitive general proof of the continuous version of the Induced Removal Lemma based on the compactness theorem for propositional calculus. Use is made of the notion of open interpretation that often allows one to transfer methods and results from one situation to another. Again, it is shown that some previous arguments can be quite naturally framed using this language.Bibliography: 68 titles.

作者简介

Leonardo Coregliano

University of Chicago

Email: lenacore@uchicago.edu

Alexander Razborov

University of Chicago; Steklov Mathematical Institute of Russian Academy of Sciences; Toyota Technological Institute at Chicago

Email: razborov@mi-ras.ru
Doctor of physico-mathematical sciences, no status

参考

  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
下载

版权所有 © Coregliano L.N., Razborov A.A., 2020

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

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