{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T16:13:42Z","timestamp":1775837622645,"version":"3.50.1"},"reference-count":40,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":1288,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2010,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A set <jats:italic>A<\/jats:italic> of vertices of a graph <jats:italic>G<\/jats:italic> is called <jats:italic>d<\/jats:italic>-scattered in <jats:italic>G<\/jats:italic> if no two <jats:italic>d<\/jats:italic>-neighborhoods of (distinct) vertices of <jats:italic>A<\/jats:italic> intersect. In other words, <jats:italic>A<\/jats:italic> is <jats:italic>d<\/jats:italic>-scattered if no two distinct vertices of <jats:italic>A<\/jats:italic> have distance at most <jats:italic>2d.<\/jats:italic> 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.<\/jats:p>","DOI":"10.2178\/jsl\/1278682204","type":"journal-article","created":{"date-parts":[[2010,7,9]],"date-time":"2010-07-09T13:30:45Z","timestamp":1278682245000},"page":"868-887","source":"Crossref","is-referenced-by-count":45,"title":["First order properties on nowhere dense structures"],"prefix":"10.1017","volume":"75","author":[{"given":"Jaroslav","family":"Ne\u0161et\u0159il","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Patrice Ossona","family":"de Mendez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200002425_ref034","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.1970"},{"key":"S0022481200002425_ref032","volume-title":"Proc. of the fifth European Congress of Mathematics","author":"Ne\u0161et\u0159il","year":"2009"},{"key":"S0022481200002425_ref005","doi-asserted-by":"publisher","DOI":"10.1145\/1131342.1131344"},{"key":"S0022481200002425_ref027","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2007.11.019"},{"key":"S0022481200002425_ref020","first-page":"55","article-title":"Aspects algorithmiques des classes d'expansion born\u00e9e","volume":"1372","author":"Ne\u0161et\u0159il","year":"2005","journal-title":"7e Journ\u00e9es Graphes et Algorithmes"},{"key":"S0022481200002425_ref024","first-page":"223","article-title":"Fraternal augmentations of graphs, coloration and minors, Proceedings of the Sixth Czech-Slovak International Symposium on Combinatorics","volume":"28","author":"Ne\u0161et\u0159il","year":"2007","journal-title":"Graph Theory, Algorithms and Applications"},{"key":"S0022481200002425_ref018","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-07003-1"},{"key":"S0022481200002425_ref017","doi-asserted-by":"publisher","DOI":"10.1007\/10703163_9"},{"key":"S0022481200002425_ref016","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511551574"},{"key":"S0022481200002425_ref015","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001"},{"key":"S0022481200002425_ref014","volume-title":"Computation and proof theory","author":"Gurevich","year":"1984"},{"key":"S0022481200002425_ref013","volume-title":"Finite model theory","author":"Ebbinghaus","year":"1996"},{"key":"S0022481200002425_ref010","volume-title":"Proc. 22nd IEEE Symp. on Logic in Computer Science","author":"Dawar","year":"2007"},{"key":"S0022481200002425_ref033","article-title":"Characterizations and examples of graph classes with bounded expansion","author":"Ne\u0161et\u0159il","year":"2009","journal-title":"European Journal of Combinatorics"},{"key":"S0022481200002425_ref009","volume-title":"On preservation theorems in finite model theory","author":"Dawar","year":"2007"},{"key":"S0022481200002425_ref004","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055602"},{"key":"S0022481200002425_ref001","doi-asserted-by":"publisher","DOI":"10.1145\/31846.31852"},{"key":"S0022481200002425_ref021","first-page":"101","volume-title":"7th International Colloquium on Graph Theory","volume":"22","author":"Ne\u0161et\u0159il","year":"2005"},{"key":"S0022481200002425_ref029","volume-title":"Building bridges between mathematics and computer science","volume":"19","author":"Ne\u0161et\u0159il","year":"2008"},{"key":"S0022481200002425_ref025","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2006.07.013"},{"key":"S0022481200002425_ref011","unstructured":"Dvo\u0159\u00e1k Z. , Asymptotical structure of combinatorial objects, Ph.D. thesis, Charles University, Faculty of Mathematics and Physics, 2007."},{"key":"S0022481200002425_ref019","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1959.9.129"},{"key":"S0022481200002425_ref008","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74456-6_2"},{"key":"S0022481200002425_ref003","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_116"},{"key":"S0022481200002425_ref037","doi-asserted-by":"publisher","DOI":"10.1145\/1379759.1379763"},{"key":"S0022481200002425_ref035","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480104445630"},{"key":"S0022481200002425_ref036","volume-title":"5th Symp. Discrete Algorithms. SIAM","author":"Plotkin","year":"1994"},{"key":"S0022481200002425_ref023","first-page":"76","volume-title":"Midsummer Combinatorial Workshop 2005 and DIMACS, DIMATIA, R\u00e9nyi Workshop 2005","volume":"2006","author":"Ne\u0161et\u0159il","year":"2006"},{"key":"S0022481200002425_ref026","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2006.07.014"},{"key":"S0022481200002425_ref002","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-63246-8_2"},{"key":"S0022481200002425_ref030","first-page":"393","volume-title":"Graph Theory and Applications (EuroComb 2009)","volume":"34","author":"Ne\u0161et\u0159il","year":"2009"},{"key":"S0022481200002425_ref007","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"S0022481200002425_ref012","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2007.05.008"},{"key":"S0022481200002425_ref006","volume-title":"Graphes","author":"Berge","year":"1983"},{"key":"S0022481200002425_ref031","unstructured":"Ne\u0161et\u0159il J. and de Mendez P. Ossona , Counting subgraphs in graphs, in preparation, 2009."},{"key":"S0022481200002425_ref028","article-title":"On nowhere dense graphs","author":"Ne\u0161et\u0159il","year":"2008","journal-title":"European Journal of Combinatorics"},{"key":"S0022481200002425_ref040","volume-title":"Discrete Mathematics","author":"Zhu"},{"key":"S0022481200002425_ref038","first-page":"324","volume-title":"Proc. 10th IEEE Symp. on Logic in Computer Science","author":"Stolboushkin","year":"1995"},{"key":"S0022481200002425_ref022","first-page":"391","volume-title":"STOC'06. Proceedings of the 38th Annual ACM Symposium on Theory of Computing","author":"Ne\u0161et\u0159il","year":"2006"},{"key":"S0022481200002425_ref039","first-page":"15","volume":"24","author":"Tait","year":"1959","journal-title":"A counterexample to a conjecture of Scott and Suppes"}],"container-title":["The Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200002425","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T21:39:23Z","timestamp":1556401163000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200002425\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9]]},"references-count":40,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,9]]}},"alternative-id":["S0022481200002425"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1278682204","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,9]]}}}