Random lifts of graphs: Independence and chromatic number

For a graph G , a random n ‐lift of G has the vertex set V ( G )×[ n ] and for each edge [ u , v ] ∈ E ( G ), there is a random matching between { u }×[ n ] and { v }×[ n ]. We present bounds on the chromatic number and on the independence number of typical random lifts, with G fixed and n →∞. For the independence number, upper and lower bounds are obtained as solutions to certain optimization problems on the base graph. For a base graph G with chromatic number χ and fractional chromatic number χ f , we show that the chromatic number of typical lifts is bounded from below by const ⋅ \documentclass{article}\pagestyle{empty}\begin{document}$\sqrt{\chi/\log\chi}$ and also by const ⋅ χ f /log 2 χ f (trivially, it is bounded by χ from above). We have examples of graphs where the chromatic number of the lift equals χ almost surely, and others where it is a.s. O (χ/logχ). Many interesting problems remain open. © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 1–22, 2002