Tag Archives: Combinatorics

Important formulas in Combinatorics

Another spin-off of the Noga-poster-formula-competition is a MathOverflow question:  Important formulas in combinatorics.

The question collects important formulas representing major progress in combinatorics.

So far there are 31 formulas and quite a few were new to me. There are several areas of combinatorics that are not yet represented. As is natural, many formulas come from enumerative combinatorics. Don’t hesitate to contribute (best – on MathOverflow) more formulas!

Here are a few:combform

Amazing: Peter Keevash Constructed General Steiner Systems and Designs

KONICA MINOLTA DIGITAL CAMERA

Here is one of the central and oldest problems in combinatorics:

Problem: Can you find a collection S of q-subsets from an n-element set X set so that every r-subset of X is included in precisely λ sets in the collection?

A collection S  of this kind are called a design of parameters (n,q,r, λ),  a special interest is the case  λ=1, and in this case S is called a Steiner system.

For such an S to exist n should be admissible namely {{q-i} \choose {r-i}} should divide \lambda {{n-i} \choose {r-i}} for every 1 \le i \le r-1.

There are only few examples of designs when r>2. It was even boldly conjectured that for every q r and λ if n is sufficiently large than a design of parameters  (n,q,r, λ) exists but the known constructions came very very far from this.   … until last week. Last week, Peter Keevash gave a twenty minute talk at Oberwolfach where he announced the proof of the bold existence conjecture. Today his preprint the existence of designs, have become available on the arxive.

Brief history

The existence of designs and Steiner systems is one of the oldest and most important problems in combinatorics.

1837-1853 – The existence of designs and Steiner systems was asked by Plücker(1835), Kirkman (1846) and Steiner (1853).

1972-1975 – For r=2 which was of special interests, Rick Wilson proved their existence for large enough admissible values of n.

1985 -Rödl proved the existence of approximate objects (the property holds for (1-o(1)) r-subsets of X) , thus answering a conjecture by Erdös and Hanani.

1987  – Teirlink proved their existence for infinitely  many values of n when r and q are arbitrary and  λ is a certain large number depending on q and r but not on n. (His construction also does not have repeated blocks.)

2014 – Keevash’s  proved the existence of Steiner systems for all but finitely many admissible  values of n for every q and r. He uses a new method referred to as Randomised Algebraic Constructions.

Update: Just 2 weeks before Peter Keevash announced his result I mentioned the problem in my lecture in “Natifest” in a segment of the lecture devoted to the analysis of Nati’s dreams. 35:38-37:09.

Update: Some other blog post on this achievement: Van Vu Jordan Ellenberg, The aperiodical . A related post from Cameron’s blog Subsets and partitions.

Update: Danny Calegary pointed out a bird-eye similarity between Keevash’s strategy and the strategy of the  recent Kahn-Markovic proof of the Ehrenpreis conjecture http://arxiv.org/abs/1101.1330 , a strategy used again by Danny and Alden Walker to show that random groups contain fundamental groups of closed surfaces http://arxiv.org/abs/1304.2188 .

Jerusalem Combinatorics ’93

Jerusalem Combinatorics ’93 is the title of a conference I organized that took place fifteen years ago in May 9-17, 1993 at the Hebrew University of Jerusalem. It was a conference that was devoted to all areas of combinatorics. The other organizers were Noga Alon, Hélène Barcelo, Anders Björner, and Edna Wigderson. Altogether there were around thirty plenary talks, and about fifty additional invited talks in 10 sections representing various subareas of combinatorics. There were also four special talks for a large audience. Overall, it was a fruitful and a very nice event that I think people enjoyed.

A special aspect of the conference was the unusually large number of female speakers. 16 out of the 30 main plenary speakers were women, and also many of the additional speakers,  special session organizers, and other participants. The four large audience lecturers were Vera Sós, who talked about irregularities of distributions, Mireille Bousquet-Mélou who talked about polyominoes, Hillel Furstenberg who talked about Ergodic theory and Combinatorics, and Joan Birman who talked about the combinatorics of finite-type invariants for knots.

collection of papers   by participants of the conference, edited by Barcelo and myself, appeared as Volume 178 of Contemporary  Mathematics.

The poster of the conference also has an interesting story behind it. Continue reading

Combinatorics, Mathematics, Academics, Polemics, …

1. About:

My name is Gil Kalai and I am a mathematician working mainly in the field of Combinatorics.  Within combinatorics, I work mainly on geometric combinatorics and the study of convex polytopes and related objects, and on the analysis of Boolean functions and related matters. I am a professor at the Institute of Mathematics at the Hebrew University of Jerusalem and also have a  long-term visiting position at the departments of Computer Science and Mathematics at Yale University, New Haven.  

 

 

 

 

 

 

 

 Gosset polytope– a hand drawing by Peter McMullen of the plane projection of the 8-dimensional 4-simplicial 4-simple Gosset polytope. Continue reading