Minors in lifts of graphs

We study here lifts and random lifts of graphs, as defined by Amit and Linial (Combinatorica 22 (2002), 1–18). We consider the Hadwiger number η and the Hajós number σ of ?‐lifts of Kⁿ and analyze their extremal as well as their typical values (that is, for random lifts). When ? = 2, we show that , and random lifts achieve the lower bound (as n → ∞). For bigger values of ?, we show . We do not know how tight these bounds are, and in fact, the most interesting question that remains open is whether it is possible for η to be o(n). When ? < O(log n), almost every ?‐lift of Kⁿ satisfies η = Θ(n) and for , almost surely . For bigger values of ?, almost always. The Hajós number satisfies , and random lifts achieve the lower bound for bounded ? and approach the upper bound when ? grows. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006