Premium
Random lifts of graphs: Independence and chromatic number
Author(s) -
Amit Alon,
Linial Nathan,
Matoušek Jiří
Publication year - 2002
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.10003
Subject(s) - combinatorics , mathematics , independence number , bounded function , chromatic scale , vertex (graph theory) , random graph , graph , lift (data mining) , discrete mathematics , upper and lower bounds , computer science , mathematical analysis , data mining
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