Interpreting nowhere dense graph classes as a classical notion of model theory

Article English OPEN
Adler, H ; Adler, I (2014)
  • Publisher: Elsevier
  • Subject:
    acm: MathematicsofComputing_DISCRETEMATHEMATICS

A class of graphs is nowhere dense if for every integer r there is a finite upper bound on the size of complete graphs that occur as r-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.
  • References (15)
    15 references, page 1 of 2

    [1] Hans Adler. Introduction to theories without the independence property. Arch. Math. Log. accepted.

    [2] Anuj Dawar. Finite model theory on tame classes of structures. In Ludek Kuˇcera and Anton´ın Kuˇcera, editors, MFCS, volume 4708 of Lect. Notes Comput. Sc., pages 2-12. Springer, 2007.

    [3] Anuj Dawar. Homomorphism preservation on quasi-wide classes. J. Comput. Syst. Sci., 76(5):324-332, 2010.

    [4] Anuj Dawar and Stephan Kreutzer. Domination problems in nowhere-dense classes. In Ravi Kannan and K. Narayan Kumar, editors, FSTTCS, volume 4 of LIPIcs, pages 157-168. Schloss Dagstuhl - Leibniz-Zentrum fu¨r Informatik, 2009.

    [5] Reinhard Diestel. Graph Theory, volume 173 of Grad. Texts in Math. Springer, 2005.

    [6] Doug Ensley and Rami Grossberg. Finite models, stability, and Ramsey's theorem, 1996.

    [7] Martin Grohe and Gy¨orgy Tur´an. Learnability and definability in trees and similar structures. Theory Comput. Syst., 37(1):193- 220, 2004.

    [8] Heinrich Herre, Alan H. Mekler, and Kenneth W. Smith. Superstable graphs. Fund. Math., 118:75-79, 1983.

    [9] Wilfrid Hodges. A Shorter Model Theory. Cambridge University Press, 1997.

    [10] M. Chris Laskowski. Vapnik-Chervonenkis classes of definable sets. J. London Math. Soc. (2), 45:377-384, 1992.

  • Metrics
    views in OpenAIRE
    views in local repository
    downloads in local repository

    The information is available from the following content providers:

    From Number Of Views Number Of Downloads
    White Rose Research Online - IRUS-UK 0 30
Share - Bookmark