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 n and analyze their extremal as well as their typical values (that is, for random lifts). When ℓ = 2, we show that ${n \over 2} \leq \eta \leq n$ , and random lifts achieve the lower bound (as n → ∞). For bigger values of ℓ, we show $\Omega({n \over {\sqrt{\log n}}}) \leq \eta \leq n\sqrt{\ell}$ . 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 n satisfies η = Θ( n ) and for $\Omega(\log{n}) \leq \ell \leq n^{{1 \over 3} - \varepsilon}$ , almost surely $\eta = \Theta({n\sqrt{\ell} \over {\sqrt{\log{n}}}})$ . For bigger values of ℓ, $\Omega({n\sqrt{\ell} \over {\sqrt{\log{\ell}}}}) \leq \eta \leq n\sqrt{\ell}$ almost always. The Hajós number satisfies $\Omega(\sqrt{n}) \leq \sigma \leq n$ , and random lifts achieve the lower bound for bounded ℓ and approach the upper bound when ℓ grows. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006