Russian Mathematical Surveys
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor
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


Russian Mathematical Surveys, 2020, Volume 75, Issue 4, Pages 627–723
DOI: https://doi.org/10.1070/RM9956
(Mi rm9956)
 

This article is cited in 8 scientific papers (total in 8 papers)

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
References:
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.
Received: 29.01.2020
Russian version:
Uspekhi Matematicheskikh Nauk, 2020, Volume 75, Issue 4(454), Pages 45–152
DOI: https://doi.org/10.4213/rm9956
Bibliographic databases:
Document Type: Article
UDC: 510.67+519.212.2+519.112.7
MSC: Primary 05C35, 05C65, 05D40; Secondary 05C20, 05C99, 05D99, 60C99
Language: English
Original paper language: Russian
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/rm9956}
\crossref{https://doi.org/10.4213/rm9956}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4153699}
\zmath{https://zbmath.org/?q=an:1498.03068}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2020RuMaS..75..627C}
\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{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000586804500001}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85094953063}
Linking options:
  • https://www.mathnet.ru/eng/rm9956
  • https://doi.org/10.1070/RM9956
  • https://www.mathnet.ru/eng/rm/v75/i4/p45
  • This publication is cited in the following 8 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Успехи математических наук Russian Mathematical Surveys
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024