Large expanders in high genus unicellular maps

DOI10.5070/C62359155MaRDI QIDQ5051457zbMATH OpenOpenAlexFDO

Authors Baptiste Louf

Publication date 23 November 2022

Published in Combinatorial Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2102.11680

zbMATH Keywords

combinatorial mapsexpander graphshigh genus

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Expander graphs (05C48) Combinatorial probability (60C05) Geometric probability and stochastic geometry (60D05)

Abstract: We study large uniform random maps with one face whose genus grows linearly with the number of edges. They can be seen as a model of discrete hyperbolic geometry. In the past, several of these hyperbolic geometric features have been discovered, such as their local limit or their logarithmic diameter. In this work, we show that with high probability such a map contains a very large induced subgraph that is an expander.

Recommendations

• Large unicellular maps in high genus
• Short cycles in high genus unicellular maps
• Unicellular maps vs. hyperbolic surfaces in large genus: simple closed curves
• The local limit of unicellular maps in high genus
• Local limits of bipartite maps with prescribed face degrees in high genus

Cites work

• A Bijection for Rooted Maps on Orientable Surfaces
• A bijection for triangulations, quadrangulations, pentagulations, etc.
• A Census of Planar Maps
• A Census of Planar Triangulations
• A generic method for bijections between blossoming trees and planar maps
• A simple model of trees for unicellular maps
• Analytic combinatorics
• Blossoming bijection for higher-genus maps
• Counting rooted maps by genus. I
• Expander graphs and their applications
• Factoring \(n\)-cycles and counting maps of given genus
• Geodesics in Brownian surfaces (Brownian maps)
• Isoperimetry and heat kernel decay on percolation clusters.
• Large unicellular maps in high genus
• Local limits of bipartite maps with prescribed face degrees in high genus
• Local limits of uniform triangulations in high genus
• Lower bounds for the isoperimetric numbers of random regular graphs
• On a surface formed by randomly gluing together polygonal discs
• Planar maps as labeled mobiles
• Planarity and non-separating cycles in uniform high genus quadrangulations
• The asymptotic number of rooted maps on a surface
• The Brownian map is the scaling limit of uniform random plane quadrangulations
• The local limit of unicellular maps in high genus
• Uniform infinite planar triangulations
• Uniqueness and universality of the Brownian map
• Universality for random surfaces in unconstrained genus

Cited in

(7)

• Short cycles in high genus unicellular maps
• Hyperbolic and parabolic unimodular random maps
• Finding large expanders in graphs: from topological minors to induced subgraphs
• Unicellular maps vs. hyperbolic surfaces in large genus: simple closed curves
• Distances and isoperimetric inequalities in random triangulations of high genus
• Length spectrum of large genus random metric maps
• Large unicellular maps in high genus

This page was built for publication: Large expanders in high genus unicellular maps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5051457)