Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Adler, H; Adler, I (2014)
Publisher: Elsevier
Languages: English
Types: Article

Classified by OpenAIRE into

ACM Ref: 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.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • [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.
    • [11] Jaroslav Nesetril and Patrice Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics. Springer, 2012.
    • [12] Klaus-Peter Podewski and Martin Ziegler. Stable graphs. Fund. Math., 100:101-107, 1978.
    • [13] Jaroslav Neˇsetˇril and Patrice Ossona de Mendez. First order properties on nowhere dense structures. J. Symb. Logic, 75:868-887, 2010.
    • [14] Jaroslav Neˇsetˇril and Patrice Ossona de Mendez. On nowhere dense graphs. Eur. J. Comb., 32(4):600-617, 2011.
    • [15] Saharon Shelah. Classification Theory and the Number of NonIsomorphic Models. Stud. Logic Found. Math. North-Holland, 2nd edition, 1990.
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article