A Lower Bound on the Hadwiger Number of a Random Subgraph of the Kneser Graph

For n, k in the natural numbers, let G = KG(n, k) be the usual Kneser graph (whose vertices are k–sets of {1, 2, . . . , n} with A ∼ B if and only if A ∩ B = ∅). The Hadwiger number of a graph H, denoted h(H), is max{t : Kt is a minor of H}. In “Lower Bound of the Hadwiger Number of Graphs by their Average Degree,” Kostochka gives a lower bound on t with respect to the average degree of a graph H. Now, let Gp be the usual binomial random subgraph of G. In this paper, we give a general lower bound on h(Gp) as n → ∞ with k \u3c\u3c √n; indeed, if k and p satisfy certain conditions, our lower bound is larger than previous lower bounds