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






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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
Received: 29.01.2020

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}


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

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Успехи математических наук Russian Mathematical Surveys
    Number of views:
    This page:174
    References:15
    First page:16

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021