Conjecture that LPS graphs are lossless expanders

At least 4 years old · documented by

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 Y⊂XnY\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 Y⊂XnY\subset X_n with

∣Y∣≤∣Xn∣1−ϵ,|Y|\leq |X_n|^{1-\epsilon},

we have

∣N(Y)∣≥(q+1−o(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.

References

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.