#### Vol. 12, No. 7, 2019

 Recent Issues
 The Journal About the Journal Editorial Board Subscriptions Editors’ Interests Scientific Advantages Submission Guidelines Submission Form Ethics Statement Editorial Login ISSN: 1944-4184 (e-only) ISSN: 1944-4176 (print) Author Index Coming Soon Other MSP Journals
On the Hadwiger number of Kneser graphs and their random subgraphs

### Arran Hamm and Kristen Melton

Vol. 12 (2019), No. 7, 1153–1161
##### Abstract

For $n,k\in ℕ$, let $KG\left(n,k\right)$ be the usual Kneser graph (whose vertices are $k$-sets of $\left\{1,2,\dots ,n\right\}$ with $A\sim B$ if and only if $A\cap B=\varnothing$). The Hadwiger number of a graph $G$, denoted by $h\left(G\right)$, is $max\left\{t:{K}_{t}\preccurlyeq G\right\}$, where $H\preccurlyeq G$ if $H$ is a minor of $G$. Previously, lower bounds have been given on the Hadwiger number of a graph in terms of its average degree. In this paper we give lower bounds on $h\left(KG\left(n,k\right)\right)$ and $h\left(KG{\left(n,k\right)}_{p}\right)$, where $KG{\left(n,k\right)}_{p}$ is the binomial random subgraph of $KG\left(n,k\right)$ with edge probability $p$. Each of these bounds is larger than previous bounds under certain conditions on $k$ and $p$.

However, your active subscription may be available on Project Euclid at
https://projecteuclid.org/involve

We have not been able to recognize your IP address 35.168.62.171 as that of a subscriber to this journal.
Online access to the content of recent issues is by subscription, or purchase of single articles.

or by using our contact form.