{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,16]],"date-time":"2025-07-16T13:20:03Z","timestamp":1752672003467},"reference-count":12,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2021,5,19]],"date-time":"2021-05-19T00:00:00Z","timestamp":1621382400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2021,11]]},"abstract":"Abstract<\/jats:title>In this short note, we prove the following analog of the K\u0151v\u00e1ri\u2013S\u00f3s\u2013Tur\u00e1n theorem for intersection graphs of boxes. If G<\/jats:italic> is the intersection graph of n<\/jats:italic> axis-parallel boxes in $${{\\mathbb{R}}^d}$$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> such that G<\/jats:italic> contains no copy of K<\/jats:italic>t,t<\/jats:italic><\/jats:sub>, then G<\/jats:italic> has at most ctn<\/jats:italic>( log n<\/jats:italic>)2d<\/jats:italic>+3<\/jats:sup> edges, where c<\/jats:italic> = c<\/jats:italic>(d<\/jats:italic>)>0 only depends on d<\/jats:italic>. Our proof is based on exploring connections between boxicity, separation dimension and poset dimension. Using this approach, we also show that a construction of Basit, Chernikov, Starchenko, Tao and Tran of K<\/jats:italic>2,2<\/jats:sub>-free incidence graphs of points and rectangles in the plane can be used to disprove a conjecture of Alon, Basavaraju, Chandran, Mathew and Rajendraprasad. We show that there exist graphs of separation dimension 4 having superlinear number of edges.<\/jats:p>","DOI":"10.1017\/s0963548321000171","type":"journal-article","created":{"date-parts":[[2021,5,19]],"date-time":"2021-05-19T04:49:19Z","timestamp":1621399759000},"page":"982-987","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":6,"title":["Tur\u00e1n-type results for intersection graphs of boxes"],"prefix":"10.1017","volume":"30","author":[{"given":"Istv\u00e1n","family":"Tomon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dmitriy","family":"Zakharov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2021,5,19]]},"reference":[{"key":"S0963548321000171_ref9","first-page":"50","article-title":"On a problem of K. Zarankiewicz. Colloq.","volume":"3","author":"K\u00f6v\u00e1ri","year":"1954","journal-title":"Math."},{"key":"S0963548321000171_ref2","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22236"},{"key":"S0963548321000171_ref7","unstructured":"[7] Janzer, O. and Pohoata, C. (2020) On the Zarankiewicz problem for graphs with bounded VC-dimension. arXiv preprint, arXiv:2009.00130."},{"key":"S0963548321000171_ref10","unstructured":"[10] Scott, A. and Wood, D. R. (2018) Separation dimension and degree. Math. Proc. Camb. Phil. Soc. 1\u201310."},{"key":"S0963548321000171_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2008.06.002"},{"key":"S0963548321000171_ref12","unstructured":"[12] Tomon, I. (2020) Ramsey properties of semilinear graphs. arXiv preprint, arXiv:2102.12464."},{"key":"S0963548321000171_ref4","doi-asserted-by":"crossref","unstructured":"[4] Davies, J. (2020) Box and segment intersection graphs with large girth and chromatic number. arXiv preprint, arXiv:2011.14174.","DOI":"10.19086\/aic.25431"},{"key":"S0963548321000171_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579194"},{"key":"S0963548321000171_ref6","doi-asserted-by":"publisher","DOI":"10.4171\/JEMS\/705"},{"key":"S0963548321000171_ref3","doi-asserted-by":"crossref","unstructured":"[3] Basit, A. , Chernikov, A. , Starchenko, S. , Tao, T. and Tran, C.-M. (2020) Zarankiewicz\u2019s problem for semilinear hypergraphs. arXiv preprint, arXiv:2009.02922.","DOI":"10.1017\/fms.2021.52"},{"key":"S0963548321000171_ref8","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/342\/06137"},{"key":"S0963548321000171_ref1","doi-asserted-by":"publisher","DOI":"10.1137\/100786290"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548321000171","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,15]],"date-time":"2021-10-15T15:52:09Z","timestamp":1634313129000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548321000171\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,19]]},"references-count":12,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,11]]}},"alternative-id":["S0963548321000171"],"URL":"https:\/\/doi.org\/10.1017\/s0963548321000171","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,19]]},"assertion":[{"value":"\u00a9 The Author(s), 2021. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}