Asymptotic dimension of intersection graphs

2022/02/15 by Dvořák, Zdeněk, Norin, Sergey · 3 citations
#05C62 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2202.07293

Abstract

We show that intersection graphs of compact convex sets in Rⁿ of bounded aspect ratio have asymptotic dimension at most 2n+1. More generally, we show this is the case for intersection graphs of systems of subsets of any metric space of Assouad-Nagata dimension n that satisfy the following condition: For each r,s>0 and every point p, the number of pairwise-disjoint elements of diameter at least s in the system that are at distance at most r from p is bounded by a function of r/s.

Cited by

• Nerve-type and invariance theorems for asymptotic dimension
• String graphs are quasi-isometric to planar graphs
• Burling graphs in graphs with large chromatic number

Related

• Nerve-type and invariance theorems for asymptotic dimension
• Strongly sublinear separators and bounded asymptotic dimension for sphere intersection graphs
• Asymptotic-Type Dimension Bounds through Combinatorial Approaches
• Surfaces have (asymptotic) dimension 2
• Short proofs of three results about intersecting systems