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, 2016, Volume 71, Issue 1(427), Pages 85–116 (Mi umn9688)  

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

Structural sparsity

J. Nešetřilab, P. Ossona de Mendezac

a Computer Science Institute of Charles University (IUUK), Prague, Czech Republic
b Computer Science Institute of Charles University (ITI), Prague, Czech Republic
c Centre d'Analyse et de Mathèmatiques Sociales (CNRS, UMR 8557), Paris, France

Abstract: The notion of structural sparsity is discussed, and its relation to the ‘nowhere dense/somewhere dense’ dichotomy introduced by the authors for classes of graphs is examined. The numerous facets of this dichotomy are surveyed, along with its connections to several concepts like stability, independence, VC-dimension, regularity partitions, entropy, class speed, low tree-depth decomposition, quasi-wideness, neighbourhood covering, subgraph statistics, and so on, as well as algorithmic complexity issues like fixed-parameter tractability of first-order model checking.
Bibliography: 78 titles.

Keywords: relational structures, graph theory, nowhere dense class, sparsity, VC-dimension, stability, independence property, shallow minor, random-free limit, structural limit, Borel structure, modelling, low tree-depth decomposition, model checking.

Funding Agency Grant Number
European Research Council ERCCZ LL-1201
Agence Nationale de la Recherche ANR-13-BS02-0007
Czech Science Foundation CE-ITI P202/12/G061
The work of the first author was supported by grants ERCCZ LL-1201 and CE-ITI P202/12/G061, and by the European Associated Laboratory “Structures in Combinatorics” (LEA STRUCO). The work of the second author was supported by grant ERCCZ LL-1201 and by the European Associated Laboratory “Structures in Combinatorics” (LEA STRUCO) and partially supported by ANR project Stint under reference ANR-13-BS02-0007.


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

Full text: PDF file (1344 kB)
References: PDF file   HTML file

English version:
Russian Mathematical Surveys, 2016, 71:1, 79–107

Bibliographic databases:

UDC: 512.56+519.71+519.17
MSC: 03C13, 03C98, 05C99
Received: 02.06.2015

Citation: J. Nešetřil, P. Ossona de Mendez, “Structural sparsity”, Uspekhi Mat. Nauk, 71:1(427) (2016), 85–116; Russian Math. Surveys, 71:1 (2016), 79–107

Citation in format AMSBIB
\Bibitem{NesOss16}
\by J.~Ne{\v s}et{\v r}il, P.~Ossona de Mendez
\paper Structural sparsity
\jour Uspekhi Mat. Nauk
\yr 2016
\vol 71
\issue 1(427)
\pages 85--116
\mathnet{http://mi.mathnet.ru/umn9688}
\crossref{https://doi.org/10.4213/rm9688}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3507464}
\zmath{https://zbmath.org/?q=an:06599755}
\adsnasa{http://adsabs.harvard.edu/cgi-bin/bib_query?2016RuMaS..71...79N}
\elib{http://elibrary.ru/item.asp?id=25707791}
\transl
\jour Russian Math. Surveys
\yr 2016
\vol 71
\issue 1
\pages 79--107
\crossref{https://doi.org/10.1070/RM9688}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000376511100002}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84973523453}


Linking options:
  • http://mi.mathnet.ru/eng/umn9688
  • https://doi.org/10.4213/rm9688
  • http://mi.mathnet.ru/eng/umn/v71/i1/p85

    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

    This publication is cited in the following articles:
    1. J. Nešetřil, P. Ossona de Mendez, “Towards a characterization of universal categories”, J. Pure Appl. Algebra, 221:8 (2017), 1899–1905  crossref  mathscinet  isi  scopus
    2. Martin A.J., Batty R., Thompson A., Kuchar R., Pancoska P., “An Examination of Children'S Motives For Triathlon Participation as a Function of Age”, Ann. Leis. Res., 22:2 (2019), 183–201  crossref  isi  scopus
    3. Nesetril J., de Mendez P.O., “Local-Global Convergence, An Analytic and Structural Approach”, Comment. Math. Univ. Carol., 60:1 (2019), 97–129  crossref  mathscinet  isi  scopus
    4. Nesetril J., De Mendez P.O., “Existence of Modeling Limits For Sequences of Sparse Structures”, J. Symb. Log., 84:2 (2019), 452–472  crossref  isi
  • Успехи математических наук Russian Mathematical Surveys
    Number of views:
    This page:351
    Full text:40
    References:61
    First page:61

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019