Geodesic
Structural sparsity
Trudy Matematicheskogo Instituta imeni V.A. Steklova, Tome 71 (2016) no. 1, pp. 79-107

Voir la notice de l'article provenant de la source Math-Net.Ru

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: graph theory, nowhere dense class, sparsity, stability, independence property, shallow minor, random-free limit, structural limit, modelling, low tree-depth decomposition, model checking.
Mots-clés : relational structures, VC-dimension, Borel structure 
@article{RM_2016_71_1_a1,
     author = {J. Ne\v{s}et\v{r}il and P. Ossona de Mendez},
     title = {Structural sparsity},
     journal = {Trudy Matematicheskogo Instituta imeni V.A. Steklova},
     pages = {79--107},
     publisher = {mathdoc},
     volume = {71},
     number = {1},
     year = {2016},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/RM_2016_71_1_a1/}
}
TY  - JOUR
AU  - J. Nešetřil
AU  - P. Ossona de Mendez
TI  - Structural sparsity
JO  - Trudy Matematicheskogo Instituta imeni V.A. Steklova
PY  - 2016
SP  - 79
EP  - 107
VL  - 71
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/RM_2016_71_1_a1/
LA  - en
ID  - RM_2016_71_1_a1
ER  - 
%0 Journal Article
%A J. Nešetřil
%A P. Ossona de Mendez
%T Structural sparsity
%J Trudy Matematicheskogo Instituta imeni V.A. Steklova
%D 2016
%P 79-107
%V 71
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/RM_2016_71_1_a1/
%G en
%F RM_2016_71_1_a1
J. Nešetřil; P. Ossona de Mendez. Structural sparsity. Trudy Matematicheskogo Instituta imeni V.A. Steklova, Tome 71 (2016) no. 1, pp. 79-107. http://geodesic.mathdoc.fr/item/RM_2016_71_1_a1/