Large expander conjecture for high-genus triangulations

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.

Sources & referencesView supporting material

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.