Turán-type results for intersection graphs of boxes. (19th November 2021)

• Record Type: Journal Article
• Authors: Tomon, István; Zakharov, Dmitriy
• Is Part Of: Combinatorics, probability and computing. Volume 30:Number 6(2021)
• Page Start: 982
• Page End: 987
• Publication Date: 2021-11-19
• Subjects: 05C10 -- 05C35; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548321000171
• Languages: English
• ISSNs: 0963-5483

Abstract

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 $${{\mathbb{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.