On the Bandwidth of the Kneser Graph

2015/12/22 by Tao Jiang, Jiang, Tao, Zevi Miller +3
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1512.06937

arxiv created 2015/12/22 · arxiv updated 2015/12/23

Abstract

Let G = (V,E) be a graph on n vertices and f: V→ [1,n] a one to one map of V onto the integers 1 through n. Let dilation(f) = max\ |f(v) - f(w)|: vw∈ E \. Define the \it bandwidth B(G) of G to be the minimum possible value of dilation(f) over all such one to one maps f. Next define the \it Kneser Graph K(n,r) to be the graph with vertex set \binom[n]r, the collection of r-subsets of an n element set, and edge set E = \ vw: v,w∈ \binom[n]r, v∩ w = ∅ \. For fixed r≥ 4 and n→ ∞ we show that B(K(n,r)) = \binomnr - (1)/(2)\binomn-1r-1 - 2\fracn^r-2(r-2)! + (r + 2)\fracn^r-3(r-3)! + O(n^r-4).

Related

• Bandwidth theorem for random graphs
• A bandwidth theorem for graph transversals
• Embedding multidimensional grids into optimal hypercubes
• Edge-bandwidth of graphs
• Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)