First order properties on nowhere dense structures

Journal of Symbolic Logic 75 (3):868-887 (2010)
  Copy   BIBTEX

Abstract

A set A of vertices of a graph G is called d-scattered in G if no two d-neighborhoods of (distinct) vertices of A intersect. In other words, A is d-scattered if no two distinct vertices of A have distance at most 2d. This notion was isolated in the context of finite model theory by Ajtai and Gurevich and recently it played a prominent role in the study of homomorphism preservation theorems for special classes of structures (such as minor closed classes). This in turn led to the notions of wide, almost wide and quasi-wide classes of graphs. It has been proved previously that minor closed classes and classes of graphs with locally forbidden minors are examples of such classes and thus (relativized) homomorphism preservation theorem holds for them. In this paper we show that (more general) classes with bounded expansion and (newly defined) classes with bounded local expansion and even (very general) nowhere dense classes are quasi wide. This not only strictly generalizes the previous results but it also provides new proofs and algorithms for some of the old results. It appears that bounded expansion and nowhere dense classes are perhaps a proper setting for investigation of wide-type classes as in several instances we obtain a structural characterization. This also puts classes of bounded expansion in the new context. Our motivation stems from finite dualities. As a corollary we obtain that any homomorphism closed first order definable property restricted to a bounded expansion class is a restricted duality

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 74,466

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

First Order Logic with Empty Structures.Mohamed A. Amer - 1989 - Studia Logica 48 (2):169 - 177.
The Block Relation in Computable Linear Orders.Michael Moses - 2011 - Notre Dame Journal of Formal Logic 52 (3):289-305.
Some Considerations on Non-Linear Time Intervals.El?Bieta Hajnicz - 1995 - Journal of Logic, Language and Information 4 (4):335-357.
Against Functional Reductionism in Cognitive Science.Muhammad Ali Khalidi - 2005 - International Studies in the Philosophy of Science 19 (3):319 – 333.
A Higher-Order Problem of Causal Relevance?Cei Maslen - 2008 - Proceedings of the Xxii World Congress of Philosophy 15:149-157.
Kinds of Objects and Varieties of Properties.Antigone M. Nounou - forthcoming - In Elaine Landry & Dean Rickles (eds.), Structures, Objects and Causality. Springer.

Analytics

Added to PP
2010-09-12

Downloads
21 (#536,822)

6 months
1 (#417,143)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

A Counterexample to a Conjecture of Scott and Suppes.W. W. Tait - 1959 - Journal of Symbolic Logic 24 (1):15-16.

Add more references