On the Hadwiger number of Kneser graphs and their random subgraphs

Hamm, Arran; Melton, Kristen

doi:10.2140/involve.2019.12.1153

Download this article
	For screen
	For printing

Recent Issues

The Journal

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

This article is available for purchase or by subscription. See below.

On the Hadwiger number of Kneser graphs and their random subgraphs

Arran Hamm and Kristen Melton

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

DOI: 10.2140/involve.2019.12.1153

Abstract

For $n, k \in ℕ$ , let $KG (n, k)$ be the usual Kneser graph (whose vertices are $k$ -sets of ${1, 2, \dots, n}$ with $A \sim B$ if and only if $A \cap B = \emptyset$ ). The Hadwiger number of a graph $G$ , denoted by $h (G)$ , is $max {t : K_{t} ≼ G}$ , where $H ≼ 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 (KG (n, k))$ and $h (KG {(n, k)}_{p})$ , where $KG {(n, k)}_{p}$ is the binomial random subgraph of $KG (n, k)$ with edge probability $p$ . Each of these bounds is larger than previous bounds under certain conditions on $k$ and $p$ .

PDF Access Denied

We have not been able to recognize your IP address 13.59.130.130 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-recommendation 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

Vol. 12, No. 7, 2019