Preview: The solution by Keller and Lifshitz to several open problems in extremal combinatorics

Peter Frankl (right) and Zoltan Furedi

The news

A new paper by Nathan Keller and Noam Lifshitz settles several open problems in extremal combinatorics for wide range of parameters. Those include the three problems we mention next.

Three central open problems in extremal combinatorics are

The 1975 Erdős-Sós forbidding one intersection problem, asks for the maximal
size of a k-uniform hypergraph that does not contain two edges whose intersection
is of size exactly t−1;

The 1987 Frankl-Füredi special simplex problem asks for the maximal
size of a k-uniform hypergraph that does not contain the following forbidden configuration: d+1 edges E_1,\dots ,E_{d+1} such that there exists a set S= \{v_1,\dots , v_{d+1}\} for which E_i\cap S = S \backslash \{v_i\} for any i and the sets {Ei \ S} are pairwise disjoint.

The 1974 Erdős-Chvátal’s simplex conjecture proposes an answer for the maximal
size of a k-uniform hypergraph that does not contain a d-simplex. Here, a d-simplex is a family of d+1 sets that have empty intersection, such that the intersection
of any d of them is nonempty.

All these questions are related to the Erdős-Ko-Rado theorem (see this post and many others). For t=1, two edges whose intersection is of size exactly t−1 are just two disjoint edges and so is a 1-simplex and a special 1-simplex.

The papers by Keller and Lifshitz and by Ellis, Keller, and Lifshitz

The paper by Keller and Lifshitz settles all these problems for a wide range of parameters! A subsequent paper by David Ellis, Nathan Keller, and Noam Lifshitz extends (among various other results) the range of parameters for the  Erdős-Sós problem even further.

Plans for posts

Michel Deza

I have an ambitious plan to devote two or three posts to these developments (but not before January). In the first post I will give some general background on Turan’s problem for hypergraphs and the new new exciting results, Then (perhaps in a second post) I will give little background on two major methods, the Delta-system method initiated by Deza, Erdos and Frankl and used in many earlier papers mainly by Frankl and Furedi, and the Junta method initiated by Friedgut which is used (among other ingredients) in the new paper.  Then I will write about the new results in the last post.

 Paul Erdos, Thomas Luczak, Ehud Friedgut, and Svante Janson 

Advertisements
This entry was posted in Combinatorics, Open problems, Updates and tagged , , , , , , , . Bookmark the permalink.

One Response to Preview: The solution by Keller and Lifshitz to several open problems in extremal combinatorics

  1. Pingback: Hardness of Approximating Vertex Cover, Polytope-Integrality-Gap, the Alswede-Kachaterian theorem, and More. | Combinatorics and more

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s