AN IMPROVED LOWER BOUND FOR THE EXPANSION OF RANDOM REGULAR GRAPHS THROUGH π-LIFTS
Mohammad-Hossein Shojaedin, Amir Daneshgar · HAL (Le Centre pour la Communication Scientifique Directe) · 2023
In this article we introduce a new model for random regular graphs called the iterated π-lift model, as a counterpart to the well-known iterated 2-lift model. To show the effectiveness of the π-lift construction we show that applying a random π-lift construction to a graph coming from the configuration model will give rise to a model which is not only contiguous to the configuration model itself, but also it turns out to be an asymptotic generalization of the configuration model, providing a more flexible parametric structure through which one may find better expansion lower bounds for these models, and consequently, for the uniform model of random regular graphs. Our results are based on an analysis of the corresponding optimization problems as a sequel to contributions by B. Bollobás (1988) and N. Linial et.al. (2006) on the expansion lower bounds for the configuration and the 2-lift models of random regular graphs.