CARMA Discrete Mathematics Seminar

4:00 pm

Thursday, 13th Mar 2014

V129, Mathematics Building


Prof. Brian Alspach

(CARMA, The University of Newcastle)

Dr Thomas Kalinowski

(CARMA, The University of Newcastle)

From EKR to MMS

The Erdos-Ko-Rado (EKR) Theorem is a classical result in combinatorial set theory and is absolutely fundamental to the development of extremal set theory. It answers the following question: What is the maximum size of a family F of k-element subsets of the set {1,2,...,n} such that any two sets in F have nonempty intersection?

In the 1980's Manickam, Miklos and Singhi (MMS) asked the following question: Given that a set A of n real numbers has sum zero, what is the smallest possible number of k-element subsets of A with nonnegative sum? They conjectured that the optimal solutions for this problem look precisely like the extremal families in the EKR theorem. This problem has been open for almost 30 years and many partial results have been proved. There was a burst of activity in 2012, culminating in a proof of the conjecture in October 2013.

This series of talks will explore the basic EKR theorem and discuss some of the recent results on the MMS conjecture.