A simple proof of the Hilton–Milner theorem

Let $n \geq 2 k \geq 4$ be integers and $ℱ$ a family of $k$ -subsets of ${1, 2, \dots, n}$ . We call $ℱ$ intersecting if $F \cap F^{'} \neq \emptyset$ for all $F, F^{'} \in ℱ$ , and we call $ℱ$ nontrivial if $⋂_{F \in ℱ} F = \emptyset$ . Strengthening the famous Erdős–Ko–Rado theorem, Hilton and Milner proved that $| ℱ | \leq (\binom{n - 1}{k - 1}) - (\binom{n - k - 1}{k - 1}) + 1$ if $ℱ$ is nontrivial and intersecting. We provide a proof by injection of this result.

PDF Access Denied

We have not been able to recognize your IP address 3.21.100.34 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 40.00:

Keywords

finite sets, intersection, hypergraphs

Mathematical Subject Classification 2010

Primary: 05D05

Milestones

Received: 9 October 2017

Accepted: 28 May 2018

Published: 20 May 2019

Authors

Peter Frankl
Rényi Institute Budapest Hungary

Vol. 8, No. 2, 2019

Peter Frankl

Abstract

PDF Access Denied

Keywords

Mathematical Subject Classification 2010

Milestones

Authors