2021/05/06 by Marco Caoduro, Caoduro, Marco, Lyuben Lichev +1 · 1 citation
Computer Science · #05C62 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2105.02516
openalex publication_date 2021/05/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An axis-parallel d-dimensional box is a cartesian product I1× I2× … × Ib where Ii is a closed sub-interval of the real line. For a graph G = (V,E), the boxicity of G, denoted by box(G), is the minimum dimension d such that G is the intersection graph of a family (Bv)v∈ V of d-dimensional boxes in \mathbb Rd. Let k and n be two positive integers such that n≥ 2k+1. The Kneser graph Kn(k,n) is the graph with vertex set given by all subsets of \1,2,…,n\ of size k where two vertices are adjacent if their corresponding k-sets are disjoint. In this note, we derive a general upper bound for box(Kn(k,n)), and a lower bound in the case n≥ 2k3-2k2+1, which matches the upper bound up to an additive factor of Θ(k2). Our second contribution is to provide upper and lower bounds for the boxicity of the complement of the line graph of any graph G, and as a corollary, we derive that box(Kn(2,n))∈ \n-3, n-2\ for every n≥ 5.