Turán-type results for intersection graphs of boxes

2020/09/09 by István Tomon, Tomon, István, Dmitriy Zakharov +1 · 4 citations
Mathematics · Computer Science · #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Complexity and Algorithms in Graphs

paper · pdf · doi:10.48550/arxiv.2009.04380

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 ℝ^d such that G contains no copy of K_t,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 et al. of K_2,2-free incidence graphs of points and rectangles in the plane can be used to disprove a conjecture of Alon et al. We show that there exist graphs of separation dimension 4 having superlinear number of edges.

Cited by

• On Geometric Bipartite Graphs with Asymptotically Smallest Zarankiewicz Numbers
• A simple proof of a (p,2)-theorem for non-piercing regions
• Compact Representation of Semilinear and Terrain-like Graphs
• C₄-free subgraphs of high degree with geometric applications

Related

• On the Boxicity of Kneser Graphs and Complements of Line Graphs
• On the Boxicity of Line Graphs and of Their Complements
• Neighborly boxes and strings with jokers; constructions and asymptotics
• Boxicity of Line Graphs
• Boxicity and Interval-Orders: Petersen and the Complements of Line Graphs