Conjecture that LPS graphs are lossless expanders

Let qq be fixed and large, and let XnX_n be the family of (q+1)(q+1)-regular Ramanujan graphs constructed by Lubotzky, Phillips, and Sarnak. For a vertex set YXnY\subset X_n, write N(Y)N(Y) for its neighborhood. LPS lossless-expansion conjecture. For every ϵ>0\epsilon>0, there is nn large enough such that, for every set YXnY\subset X_n with

YXn1ϵ,|Y|\leq |X_n|^{1-\epsilon},

we have

N(Y)(q+1o(q))Y.|N(Y)|\geq (q+1-o(q))|Y|.

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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.