Geodesic
Shattering, graph orientations, and connectivity
László Kozma1 ; Shay Moran2
1Saarland University, Saarbrücken
2Max Planck Institute for Informtics, Saarbrücken
The electronic journal of combinatorics, Tome 20 (2013) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We present a connection between two seemingly disparate fields: VC-theory and graph theory. This connection yields natural correspondences between fundamental concepts in VC-theory, such as shattering and VC-dimension, and well-studied concepts of graph theory related to connectivity, combinatorial optimization, forbidden subgraphs, and others.In one direction, we use this connection to derive results in graph theory. Our main tool is a generalization of the Sauer-Shelah Lemma (Pajor, 1985; Bollobás and Radcliffe, 1995; Dress, 1997; Holzman and Aharoni). Using this tool we obtain a series of inequalities and equalities related to properties of orientations of a graph. Some of these results appear to be new, for others we give new and simple proofs.In the other direction, we present new illustrative examples of shattering-extremal systems - a class of set-systems in VC-theory whose understanding is considered by some authors to be incomplete Bollobás and Radcliffe, 1995; Greco, 1998; Rónyai and Mészáros, 2011). These examples are derived from properties of orientations related to distances and flows in networks.
DOI : 10.37236/3326
Classification : 05C20, 05C40, 05D05
Mots-clés : orientations, shattering, VC-dimension, Sauer lemma, connectivity

László Kozma  1   ; Shay Moran  2

1 Saarland University, Saarbrücken
2 Max Planck Institute for Informtics, Saarbrücken 
@article{10_37236_3326,
     author = {L\'aszl\'o Kozma and Shay Moran},
     title = {Shattering, graph orientations, and connectivity},
     journal = {The electronic journal of combinatorics},
     year = {2013},
     volume = {20},
     number = {3},
     doi = {10.37236/3326},
     zbl = {1298.05145},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/3326/}
}
TY  - JOUR
AU  - László Kozma
AU  - Shay Moran
TI  - Shattering, graph orientations, and connectivity
JO  - The electronic journal of combinatorics
PY  - 2013
VL  - 20
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/3326/
DO  - 10.37236/3326
ID  - 10_37236_3326
ER  - 
%0 Journal Article
%A László Kozma
%A Shay Moran
%T Shattering, graph orientations, and connectivity
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/3326/
%R 10.37236/3326
%F 10_37236_3326
László Kozma; Shay Moran. Shattering, graph orientations, and connectivity. The electronic journal of combinatorics, Tome 20 (2013) no. 3. doi: 10.37236/3326

Cité par Sources :