TY - JOUR

T1 - Turán-type results for intersection graphs of boxes

AU - Tomon, István

AU - Zakharov, Dmitriy

N1 - Publisher Copyright:
© The Author(s), 2021. Published by Cambridge University Press.

PY - 2021

Y1 - 2021

N2 - In this short note, we prove the following analog of the Kovári-Sós-Turán theorem for intersection graphs of boxes. If G is the intersection graph of n axis-parallel boxes in Rd such that G contains no copy of Kt,t, then G has at most ctn(log n)2d+3 edges, where c = c(d)>0 only depends on d. 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 K2,2-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.

AB - In this short note, we prove the following analog of the Kovári-Sós-Turán theorem for intersection graphs of boxes. If G is the intersection graph of n axis-parallel boxes in Rd such that G contains no copy of Kt,t, then G has at most ctn(log n)2d+3 edges, where c = c(d)>0 only depends on d. 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 K2,2-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.

UR - http://www.scopus.com/inward/record.url?scp=85106441413&partnerID=8YFLogxK

U2 - 10.1017/S0963548321000171

DO - 10.1017/S0963548321000171

M3 - Article

AN - SCOPUS:85106441413

SN - 0963-5483

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

ER -