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

 Recent Issues
 The Journal About the Journal Editorial Board Editors’ Interests Subscriptions Submission Guidelines Submission Form Policies for Authors Ethics Statement 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 3.215.177.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.

Please contact your institution's librarian suggesting a subscription, for example by using our journal-recom­mendation form. Or, visit our subscription page for instructions on purchasing a subscription.

You may also contact us at contact@msp.org
or by using our contact form.

Or, you may purchase this single article for USD 30.00:

##### Keywords
Kneser graphs, Hadwiger number
##### Mathematical Subject Classification 2010
Primary: 05C83, 05C80, 05D40
##### Milestones
Received: 31 October 2018
Revised: 19 February 2019
Accepted: 11 May 2019
Published: 12 October 2019

Communicated by Anant Godbole
##### Authors
 Arran Hamm Department of Mathematics Winthrop University Rock Hill, SC United States Kristen Melton Department of Mathematics Miami University Oxford, OH United States