Journal of Symbolic Logic 75 (3):868 - 887 (2010)
AbstractA 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
Similar books and articles
The Isomorphism Problem for Computable Abelian P-Groups of Bounded Length.Wesley Calvert - 2005 - Journal of Symbolic Logic 70 (1):331 - 345.
Dual Easy Uniformization and Model-Theoretic Descriptive Set Theory.Shaughan Lavine - 1991 - Journal of Symbolic Logic 56 (4):1290-1316.
On Recursive Enumerability with Finite Repetitions.Stephan Wehner - 1999 - Journal of Symbolic Logic 64 (3):927-945.
A Borel Reducibility Theory for Classes of Countable Structures.Harvey Friedman & Lee Stanley - 1989 - Journal of Symbolic Logic 54 (3):894-914.
Quantifiers and Congruence Closure.Jörg Flum, Matthias Schiehlen & Jouko Väänänen - 1999 - Studia Logica 62 (3):315-340.
Characterizations of Negative Definability in Modal Logic.Marco Hollenberg - 1998 - Studia Logica 60 (3):357-386.
On Σ1 1 Equivalence Relations with Borel Classes of Bounded Rank.Ramez L. Sami - 1984 - Journal of Symbolic Logic 49 (4):1273 - 1283.
Characterization Classes Defined Without Equality.R. Elgueta - 1997 - Studia Logica 58 (3):357-394.
Smooth Classes Without AC and Robinson Theories.Massoud Pourmahdian - 2002 - Journal of Symbolic Logic 67 (4):1274-1294.
Freeness in Classes Without Equality.Raimon Elgueta - 1999 - Journal of Symbolic Logic 64 (3):1159-1194.
Added to PP
Historical graph of downloads
Sorry, there are not enough data points to plot this chart.