Turán-type results for intersection graphs of boxes. (19th November 2021) - Tomon, István; Zakharov, Dmitriy
Abstract: In this short note, we prove the following analog of the Kővári–Sós–Turán theorem for intersection graphs of boxes. If G is the intersection graph of n axis-parallel boxes in R^d such that G contains no copy of K t, t, then G has at most ctn ( log n ) 2 d +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 K 2, 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.