Random lifts of graphs
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].
- Random lifts of graphs are highly connected
- Cutoff for random lifts of weighted graphs
- Random lifts of graphs: perfect matchings
- The chromatic number of random lifts of \(K_5\setminus e\)
- Random lifts of \({K_5}\setminus{e}\) are 3-colorable
- Random lifts of graphs: network robustness based on the Estrada index
- Minors in lifts of graphs
- Random lifts of graphs: Independence and chromatic number
- On the number of perfect matchings in random lifts
- \(\delta\)-connectivity in random lifts of graphs
- On the expansion of group-based lifts
- Random Lifts of Graphs: Edge Expansion
- Hamilton cycles in random lifts of graphs
- A note on the trace method for random regular graphs
- Delocalized eigenvectors of transitive graphs and beyond
- Sparse high dimensional expanders via local lifts
- Random graph coverings. I: General theory and graph connectivity
- Stability of homomorphisms, coverings and cocycles. I: Equivalence
This page was built for publication: Random lifts of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2768394)
