Large expander conjecture for high-genus triangulations

About 5 years old · traced to

Let gng_n satisfy

gnn→θ∈(0,1/2),\frac{g_n}{n}\to\theta\in(0,1/2),

and let Tn,gn\mathbf{T_{n,g_n}} be a uniform triangulation of genus gng_n with 3n3n edges. An induced subgraph is a κ\kappa-expander if every set of vertices has at least κ\kappa times its size in edges leaving it. Large expander conjecture. For every ε>0\varepsilon>0, there exists a κ>0\kappa>0 depending only on ε\varepsilon and θ\theta such that, with high probability, Tn,gn\mathbf{T_{n,g_n}} contains an induced subgraph GnG_n with at least (1−ε)3n(1-\varepsilon)3n edges that is a κ\kappa-expander. This conjecture extends the paper's theorem for uniform unicellular maps to uniform triangulations, and concerns the global geometric structure of high-genus maps. It is presented as an ambitious open problem.

References

Primary source

Baptiste Louf, “Large expanders in high genus unicellular maps”, arXiv:2102.11680 (2021).

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.