A concentration inequality for the maximum vertex degree in random dissections

2022/04/04 by Kelvin Rivera-Lopez, Rivera-Lopez, Kelvin, Douglas Rizzolo +1
Mathematics · #60C05 #Advanced Combinatorial Mathematics #FOS: Mathematics #Probability (math.PR) #Random Matrices and Applications #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.2204.01687

openalex publication_date 2022/04/04 · openalex created_date 2022/04/27 · openalex updated_date 2026/07/28

Abstract

We obtain a concentration inequality for the maximum degree of a vertex in a uniformly random dissection of a polygon. This resolves a conjecture posed by Curien and Kortchemski in 2012. Our approach is based on a bijection with dual trees and the tools of analytic combinatorics.

Related

• Concentration of maximum degree in random planar graphs
• Two point concentration of maximum degree in sparse random planar graphs
• Tree/Endofunction Bijections and Concentration Inequalities
• Concentration of the maximum size of an induced subtree in moderately sparse random graphs
• Two-Point Concentration of the Domination Number of Random Graphs