Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4653613 | European Journal of Combinatorics | 2014 | 9 Pages |
Abstract
A class of graphs is nowhere dense if for every integer rr there is a finite upper bound on the size of complete graphs that occur as rr-minors. We observe that this recent tameness notion from (algorithmic) graph theory is essentially the earlier stability theoretic notion of superflatness. For subgraph-closed classes of graphs we prove equivalence to stability and to not having the independence property. Expressed in terms of PAC learning, the concept classes definable in first-order logic in a subgraph-closed graph class have bounded sample complexity, if and only if the class is nowhere dense.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Hans Adler, Isolde Adler,