{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T07:54:04Z","timestamp":1781855644469,"version":"3.54.5"},"publisher-location":"New York, NY, USA","reference-count":41,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,7,9]],"date-time":"2018-07-09T00:00:00Z","timestamp":1531094400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["UMO-2015\/19\/P\/ST6\/03998 and 2016\/21\/D\/ST6\/01485"],"award-info":[{"award-number":["UMO-2015\/19\/P\/ST6\/03998 and 2016\/21\/D\/ST6\/01485"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"name":"H2020 Marie SkBodowska-Curie Actions","award":["665778"],"award-info":[{"award-number":["665778"]}]},{"DOI":"10.13039\/501100001870","name":"Fundacja na rzecz Nauki Polskiej","doi-asserted-by":"publisher","award":["START stipend"],"award-info":[{"award-number":["START stipend"]}],"id":[{"id":"10.13039\/501100001870","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,7,9]]},"DOI":"10.1145\/3209108.3209178","type":"proceedings-article","created":{"date-parts":[[2018,6,27]],"date-time":"2018-06-27T08:14:43Z","timestamp":1530087283000},"page":"799-808","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["On the number of types in sparse graphs"],"prefix":"10.1145","author":[{"given":"Micha\u0142","family":"Pilipczuk","sequence":"first","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sebastian","family":"Siebertz","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Szymon","family":"Toru\u0144czyk","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Poland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,7,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2013.06.048"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(92)90052-M"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548303005741"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1090\/tran\/6659"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1131342.1131344"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76371"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2015.05.026"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02570718"},{"key":"e_1_3_2_1_9_1","first-page":"207","article-title":"Theory of uniform convergence of frequencies of events to their probabilities and problems of search for an optimal solution from empirical data","volume":"32","author":"Chervonenkis A.","year":"1971","unstructured":"A. Chervonenkis and V. Vapnik. 1971. Theory of uniform convergence of frequencies of events to their probabilities and problems of search for an optimal solution from empirical data. Autom. Remote Control 32 (1971), 207--217.","journal-title":"Autom. Remote Control"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.10.005"},{"key":"e_1_3_2_1_11_1","volume-title":"Kernelization and Sparseness: the Case of Dominating Set. In STACS 2016 (LIPIcs)","volume":"47","author":"Drange P\u00e5l Gr\u00f8n\u00e5s","year":"2016","unstructured":"P\u00e5l Gr\u00f8n\u00e5s Drange, Markus Sortland Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Micha\u0142 Pilipczuk, Felix Reidl, Fernando S\u00e1nchez Villaamil, Saket Saurabh, Sebastian Siebertz, and Somnath Sikdar. 2016. Kernelization and Sparseness: the Case of Dominating Set. In STACS 2016 (LIPIcs), Vol. 47. Schloss Dagstuhl---Leibniz-Zentrum f\u00fcr Informatik, 31:1--31:14. See https:\/\/arxiv.org\/abs\/1411.4575 for full proofs."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2499483"},{"key":"e_1_3_2_1_13_1","volume-title":"Neighborhood Complexity and Kernelization for Nowhere Dense Classes of Graphs. In ICALP 2017 (LIPIcs)","volume":"80","author":"Eickmeyer Kord","year":"2017","unstructured":"Kord Eickmeyer, Archontia C. Giannopoulou, Stephan Kreutzer, O-joung Kwon, Michal Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. 2017. Neighborhood Complexity and Kernelization for Nowhere Dense Classes of Graphs. In ICALP 2017 (LIPIcs), Vol. 80. Schloss Dagstuhl---Leibniz-Zentrum f\u00fcr Informatik, 63:1--63:14. See https:\/\/arxiv.org\/abs\/1612.08197 for full proofs."},{"key":"e_1_3_2_1_14_1","volume-title":"Traces of finite sets: extremal problems and geometric applications. Extremal problems for finite sets 3","author":"F\u00fcredi Zolt\u00e1n","year":"1991","unstructured":"Zolt\u00e1n F\u00fcredi and J\u00e1nos Pach. 1991. Traces of finite sets: extremal problems and geometric applications. Extremal problems for finite sets 3 (1991), 255--282."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)71879-2"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/558\/11051"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53174-7_23"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591851"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-003-1112-8"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-143-2-107-117"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/647848.736908"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039786"},{"key":"e_1_3_2_1_23_1","volume-title":"Vapnik-Chervonenkis classes of definable sets. journal of the London Mathematical Society 2, 2","author":"Laskowski Michael C","year":"1992","unstructured":"Michael C Laskowski. 1992. Vapnik-Chervonenkis classes of definable sets. journal of the London Mathematical Society 2, 2 (1992), 377--384."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2013-05820-5"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-8898-1_1"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/3116665.3117059"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2006.07.013"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1278682204"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.01.006"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/2230458"},{"key":"e_1_3_2_1_31_1","volume-title":"On the number of types in sparse graphs. arXiv preprint arXiv:1705.09336","author":"Pilipczuk Micha\u0142","year":"2017","unstructured":"Micha\u0142 Pilipczuk, Sebastian Siebertz, and Szymon Toru\u0144czyk. 2017. On the number of types in sparse graphs. arXiv preprint arXiv:1705.09336 (2017)."},{"key":"e_1_3_2_1_32_1","volume-title":"Introduction to Stability Theory","author":"Pillay Anand","unstructured":"Anand Pillay. 2008. Introduction to Stability Theory. Dover Publications."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-100-2-101-107"},{"key":"e_1_3_2_1_34_1","volume-title":"Fernando S\u00e1nchez Villaamil, and Konstantinos Stavropoulos","author":"Reidl Felix","year":"2016","unstructured":"Felix Reidl, Fernando S\u00e1nchez Villaamil, and Konstantinos Stavropoulos. 2016. Characterising Bounded Expansion by Neighbourhood Complexity. CoRR abs\/1603.09532 (2016)."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(72)90019-2"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0003-4843(71)90015-5"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1972.41.247"},{"key":"e_1_3_2_1_38_1","volume-title":"Classification theory: and the number of non-isomorphic models. Studies in Logic and the Foundations of Mathematics","author":"Shelah Saharon","unstructured":"Saharon Shelah. 1990. Classification theory: and the number of non-isomorphic models. Studies in Logic and the Foundations of Mathematics, Vol. 92. Elsevier."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"crossref","unstructured":"K. Tent and M. Ziegler. 2012. A Course in Model Theory. Cambridge University Press. https:\/\/books.google.pl\/books?id=D9sClsdErEsC","DOI":"10.1017\/CBO9781139015417"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2008.03.024"}],"event":{"name":"LICS '18: 33rd Annual ACM\/IEEE Symposium on Logic in Computer Science","location":"Oxford United Kingdom","acronym":"LICS '18","sponsor":["SIGLOG ACM Special Interest Group on Logic and Computation","IEEE-CS\\DATC IEEE Computer Society","EACSL European Association for Computer Science Logic"]},"container-title":["Proceedings of the 33rd Annual ACM\/IEEE Symposium on Logic in Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3209108.3209178","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3209108.3209178","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T07:32:46Z","timestamp":1781854366000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3209108.3209178"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,9]]},"references-count":41,"alternative-id":["10.1145\/3209108.3209178","10.1145\/3209108"],"URL":"https:\/\/doi.org\/10.1145\/3209108.3209178","relation":{},"subject":[],"published":{"date-parts":[[2018,7,9]]},"assertion":[{"value":"2018-07-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}