The Eigenvalues of the Graphs D(4,q)

2017/01/13 by Moorhouse, G. Eric, Sun, Shuying, Williford, Jason
#05C25 #05C50 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1701.03685

Abstract

The graphs D(k,q) have connected components CD(k,q) giving the best known bounds on extremal problems with \em forbidden\/ even cycles, and are denser than the well-known graphs of Lubotzky, Phillips, Sarnak and Margulis. Despite this, little about the spectrum and expansion properties of these graphs is known. In this paper we find the spectrum for k=4, the smallest open case. For each prime power q, the graph D(4,q) is q-regular graph on 2q⁴ vertices, all of whose eigenvalues other than ± q are bounded in absolute value by 2√(q). Accordingly, these graphs are good expanders, in fact very close to Ramanujan.

Related

• On the eigenvalues of the graphs D(5, q)
• Explicit expanders of every degree and size
• The limit points of the top and bottom eigenvalues of regular graphs
• High-girth near-Ramanujan graphs with localized eigenvectors
• On co-edge-regular graphs with 4 distinct eigenvalues