Turán-type results for intersection graphs of boxes

István Tomon, Dmitriy Zakharov

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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.

Original languageEnglish
JournalCombinatorics Probability and Computing
DOIs
StateAccepted/In press - 2021
Externally publishedYes

Fingerprint

Dive into the research topics of 'Turán-type results for intersection graphs of boxes'. Together they form a unique fingerprint.

Cite this