Random lifts of graphs (Q2768394)

The authors examine covering graphs of a given base graph. Their (natural) model is to randomly select a 1-factor between the fibers above vertices \(u,v\) that represents the lift of an edge \(uv\). They examine the relation between properties of the base graph and the covering graph. This paper surveys results whose proofs are provided on other manuscripts. NEWLINENEWLINENEWLINEAmong the various results presented are: (1) almost every lift of \(G\) is \(\delta (G)\)-connected, (2) upper and lower bounds on the independence number of the lift are determined as solutions to related optimization problems on the base graph, (3) lower bounds on the chromatic number of the lift are given in terms of the chromatic and fractional chromatic numbers of the base graph, and (4) conditions are given that ensure a lift either has or almost surely has a perfect matching. NEWLINENEWLINENEWLINEThe typical edge expansion of lifts of bouquets (graphs with one vertex) is examined. This allows a probabilistic proof of graphs whose edge expansion slightly exceeds previously known bounds.NEWLINENEWLINEFor the entire collection see [Zbl 0972.00057].