Conjecture that LPS graphs are lossless expanders
Conjecture that LPS graphs are lossless expanders
Let be fixed and large, and let be the family of -regular Ramanujan graphs constructed by Lubotzky, Phillips, and Sarnak. For a vertex set , write for its neighborhood. LPS lossless-expansion conjecture. For every , there is large enough such that, for every set with
we have
Lossless expansion is the optimal vertex-expansion behavior expected of these number-theoretic Ramanujan graphs. The paper's method applies to Morgenstern graphs rather than LPS graphs and suggests that the absence of suitable closed subgroups may lead to good expansion, but the conjecture is presented as unproved.
Sources & referencesView supporting material
Primary source
Amitay Kamber and Tali Kaufman, “Combinatorics via Closed Orbits: Number Theoretic Ramanujan Graphs are not Unique Neighbor Expanders”, arXiv:2103.04311 (2022).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.