{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:55:55Z","timestamp":1787324155009,"version":"build-2736575974"},"reference-count":25,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["677651"],"award-info":[{"award-number":["677651"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>We prove that for every nowhere dense class of graphs $\\mathcal{C}$, positive integer $d$, and $\\varepsilon&gt;0$, the following holds: in every $n$-vertex graph $G$ from $\\mathcal{C}$ one can find two disjoint vertex subsets $A,B\\subseteq V(G)$ such that $|A|\\geq (1\/2-\\varepsilon)\\cdot n$ and $|B|=\\Omega(n^{1-\\varepsilon})$; and either ${dist}(a,b)\\leq d$ for all $a\\in A$ and $b\\in B$, or ${dist}(a,b)&gt;d$ for all $a\\in A$ and $b\\in B$. We also show some stronger variants of this statement, including a generalization to the setting of first-order interpretations of nowhere dense graph classes.<\/jats:p>","DOI":"10.1137\/20m1342756","type":"journal-article","created":{"date-parts":[[2021,3,23]],"date-time":"2021-03-23T11:16:36Z","timestamp":1616498196000},"page":"447-464","source":"Crossref","is-referenced-by-count":4,"title":["Erd\u00f6s--Hajnal Properties for Powers of Sparse Graphs"],"prefix":"10.1137","volume":"35","author":[{"given":"Marcin","family":"Bria\u0144ski","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Piotr","family":"Micek","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9871-7509","authenticated-orcid":true,"given":"Micha\u0142 T.","family":"Seweryn","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,3,23]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2013.06.048"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2004.12.008"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21730"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1145\/2499483"},{"key":"atypb5","first-page":"10","volume":"63","author":"Eickmeyer K.","year":"2017","journal-title":"Germany"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(89)90045-0"},{"key":"atypb7","first-page":"79","author":"Fox J.","year":"2008","journal-title":"Berlin"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-010-0056-3"},{"key":"atypb9","unstructured":"J. Gajarsk\u00fd, S. Kreutzer, J. Ne\u0161et\u0159il, P. Ossona de Mendez, M. Pilipczuk, S. Siebertz, and S. Toru\u0144czyk,\n                      First-order interpretations of bounded expansion classes\n                      , in 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, LIPIcs Leibniz Int. Proc. Inform. 107, Schloss Dagstuhl, 2018, 126, Wadern, Germany,https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.126."},{"key":"atypb10","first-page":"10","volume":"15","author":"Ganian R.","year":"2019","journal-title":"Log. Methods Comput. Sci."},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1145\/3051095"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1137\/16M1079336"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/s10474-020-01074-x"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"S. Jukna,\n                      Extremal Combinatorics: With Applications in Computer Science\n                      , Texts Theoret. Comput. Sci. EATCS Ser., Springer, Berlin, 2011,https:\/\/doi.org\/10.1007\/978-3-642-17364-6.","DOI":"10.1007\/978-3-642-17364-6"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2019.103002"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2013-05820-5"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.09.008"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.37236\/9417"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2006.07.013"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2006.07.014"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.01.006"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"J. Ne\u0161et\u0159il and P. Ossona de Mendez,\n                      Sparsity: Graphs, Structures, Algorithms\n                      , Algorithms Combin. 28, Springer, Berlin, 2012,https:\/\/doi.org\/10.1007\/978-3-642-27875-4.","DOI":"10.1007\/978-3-642-27875-4"},{"key":"atypb23","unstructured":"M. Pilipczuk, M. Pilipczuk, and S. Siebertz,\n                      Lecture notes for the course \u201cSparsity\u201d given at Faculty of Mathematics, Informatics, and Mechanics of the University of Warsaw\n                      , Winter semesters 2017\/18 and 2019\/20, Warsaw,https:\/\/www.mimuw.edu.pl\/~mp248287\/sparsity2."},{"key":"atypb24","first-page":"799","author":"Pilipczuk M.","year":"2018","journal-title":"New York"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2008.03.024"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1342756","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:19:31Z","timestamp":1787321971000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1342756"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1342756"],"URL":"https:\/\/doi.org\/10.1137\/20m1342756","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}