**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 such that there exists a set for which 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 , 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 **

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