The Brown-Erdős-Sós 1973 Conjecture

Greetings from Oberwolfach.  This week, there is a great meeting here on combinatorics. In this post I want to state the Brown-Erdős-Sós conjecture and one of its variants. The trigger was a beautiful talk I heard from Lior Gishboliner on some impressive progress toward this very difficult problem.  Yet the solution of the problem seems far, and some people even doubt if the conjecture is true. Here is the paper “A New Bound for the Brown-Erdős-Sós problem” by David Conlon, Lior Gishboliner, Yevgeny Levanzov, and Asaf Shapira.

The Brown-Erdős-Sós conjecture and strong versions

Lior’s talk reminded me that Peter Frankl and Voita Rodl told me in the late 80s about strong variants of the Brown-Erdős-Sós problem that implies the Szemeredi theorem. With the kind help of Voita Rodl  who is here I can tell you about two such variants. (But I am solely responsible for all mistakes.)

Let f(n,v,e) be the largest number of edges in an 3-uniform hypergraph with n vertices and no v vertices spanning e edges or more.

Brown-Erdős-Sós Conjecture: f(n,e+3,e)=o(n^2), for every e\ge 3.

For e=3 the BES conjecture is the famous Ruzsa-Szemeredi theorem (that implies Roth’s theorem on 3-term arithmetic progressions). For e=4 the conjecture is painfully open (and is stronger than Szemeredi theorem for 4-term APs).

Here is an even stronger conjectures that implies Szemeredi theorem arithmetic progressions of arbitrary length.

Consider the following 3-uniform hypergraph H(v) with v+3 vertices and v edges: Start with a path with v+1 vertices (and v edges). Color the edges alternately with red and brown and add a red vertex and a brown vertex. Now form a 3-uniform hypergraph whose edges are the red edges of the path joined with the red vertex and the brown edges of the graph joined with the brown vertex.

Conjecture: Every H(v)-free 3-uniform hypergraph with n vertices has o(n^2) vertices.

For another strengthening of the BES-conjecture that implies the Szemeredi theorem see the paper A remark of Pisier-type theorems of Erdos, Nesetril and Rodl. Famously, the celebrated hypergraph regularity lemma (and associated counting lemma) implies another Turan type theorem for hypergraphs that in turn implies Szemeredi’s theorem and its high dimensional extensions.

The new bounds by Conlon, Gishboliner, Levanzov, and Shapira

Although the theorem is for 3-uniform hypergraph the proof relies on the hypergraph regularity lemma for higher dimensional hypergraphs.

With Voita in 1985 (or 86) and today (2020)

This entry was posted in Combinatorics and tagged , , , , , , , , , , , , , , . Bookmark the permalink.

2 Responses to The Brown-Erdős-Sós 1973 Conjecture

  1. Question: Is the bound O(n^2) obvious?

    • Lior Gishboliner says:

      Yes. If there is a pair of vertices which is contained in $e$ edges, then we have $e$ edges spanning $e+2$ vertices (which is even “better” than the $(e+3,e)$ we’re looking for). So every pair of vertices is contained in less than e edges, implying there are $O(n^2)$ edges. Actually, if you forbid an $(e+2,e)$ instead of an $(e+3,e)$, then the answer is $\Theta(n^2)$.

Leave a Reply

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

You are commenting using your 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 )

Connecting to %s