Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5777593 | Journal of Combinatorial Theory, Series B | 2017 | 20 Pages |
Abstract
The graphs D(k,q) have connected components CD(k,q) giving the best known bounds on extremal problems with forbidden even cycles, and are denser than the well-known graphs of Lubotzky, Phillips, Sarnak [14] and Margulis [15], [16]. Despite this, little is known about the spectrum and expansion properties of these graphs. 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 2q4 vertices, all of whose eigenvalues other than ±q are bounded in absolute value by 2q. Accordingly, these graphs are good expanders, in fact very close to Ramanujan.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
G. Eric Moorhouse, Shuying Sun, Jason Williford,