Uspekhi Matematicheskikh Nauk
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Subscription License agreement Submit a manuscript Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Uspekhi Mat. Nauk: Year: Volume: Issue: Page: Find

 Uspekhi Mat. Nauk, 2020, Volume 75, Issue 4(454), Pages 45–152 (Mi umn9956)

Surveys

Semantic limits of dense combinatorial objects

L. N. Coreglianoa, A. A. Razborovabc

a University of Chicago, Chicago, IL, USA
b Steklov Mathematical Institute of Russian Academy of Sciences, Moscow
c Toyota Technological Institute at Chicago, Chicago, IL, USA

Abstract: 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.

Keywords: model theory, graph limits, flag algebras, exchangeable arrays, extremal combinatorics.

DOI: https://doi.org/10.4213/rm9956

Full text: PDF file (1450 kB)
First page: PDF file
References: PDF file   HTML file

English version:
Russian Mathematical Surveys, 2020, 75:4, 627–723

Bibliographic databases:

UDC: 510.67+519.212.2+519.112.7
MSC: Primary 05C35, 05C65, 05D40; Secondary 05C20, 05C99, 05D99, 60C99

Citation: L. N. Coregliano, A. A. Razborov, “Semantic limits of dense combinatorial objects”, Uspekhi Mat. Nauk, 75:4(454) (2020), 45–152; Russian Math. Surveys, 75:4 (2020), 627–723

Citation in format AMSBIB
\Bibitem{CorRaz20} \by L.~N.~Coregliano, A.~A.~Razborov \paper Semantic limits of dense combinatorial objects \jour Uspekhi Mat. Nauk \yr 2020 \vol 75 \issue 4(454) \pages 45--152 \mathnet{http://mi.mathnet.ru/umn9956} \crossref{https://doi.org/10.4213/rm9956} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=4153699} \elib{https://elibrary.ru/item.asp?id=45176983} \transl \jour Russian Math. Surveys \yr 2020 \vol 75 \issue 4 \pages 627--723 \crossref{https://doi.org/10.1070/RM9956} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000586804500001} \scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85094953063} 

• http://mi.mathnet.ru/eng/umn9956
• https://doi.org/10.4213/rm9956
• http://mi.mathnet.ru/eng/umn/v75/i4/p45

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles
•  Number of views: This page: 174 References: 15 First page: 16