An End to the Happy Ending Problem

Andrew Suk just placed on arXiv a paper with an almost tight bound for the happy ending problem. These are exciting news for discrete geometers! I’ll use the opportunity to describe the problem and its non-technical history.

Asuk3172270-Anonymous-Statue-0
Andrew Suk and the Anonymous statue.

In the early 1930’s in Budapest, several students used to regularly meet on Sundays in a specific city park bench. This was the bench next to the statue of Anonymous, the first medieval Hungarian chronicler. Among these students were Paul Erdős, George Szekeres, and Esther Klein.

On one such Sunday meeting, Klein pointed out that for any set of five points with no three on a line, four of the points are the vertices of a convex quadrilateral. This easy observation can be proved by considering the convex hull of the five points. If at least four of the points are on the boundary of the convex hull, then we are done. If the convex hull consists only of three of the points, then we consider the line \ell  that passes through the two interior points. We take the two interior points and the two points that are on the same side of \ell  .

FivePointsES

The Budapest students started to think about whether there exists an n  such that every set of n  points with no three on a line contains the vertices of a convex pentagon. More generally, does a similar condition hold for every convex k  -gon? The first to prove the claim was Szekeres. A couple of years later, Esther Klein, who suggested the problem married George Szekeres who solved it. Since then, this problem is called the happy ending problem. They lived together up to their 90’s.

george_esther

For every integer m \ge 3  , let N(m)  denote the smallest integer such that any set of N(m)  points with no three on a line contains a subset of m  points that are the vertices of a convex m  -gon. Erdős and Szekeres published a paper on the problem in 1935. They proved that

2^{m-2}+1 \le N(m) \le \binom{2m-4}{m-2}+1.

Erdős and Szekeres conjectured that N(m)=2^{m-2}+1  , and this is sometimes called “the Erdős–Szekeres conjecture”. Erdős offered a 500$ ` for proving or disproving this conjecture, and a few years ago Ron Graham (who is handling Erdős’ problem awards) increased the amount to 1000$. So far the conjecture was verified up to m=6  by a computer. Over the years several improved bounds were published, but the improvements were always sub-exponential. That is, the value of N(m)  remained between 2^m  and 4^m  (ignoring sub-exponential factors). In his new paper, Suk derives the impressive bound N(m)\le 2^{m+4m^{4/5}}  , settling the problem up to sub-exponential factors. Surprisingly, after 81 years of small progress, Suk’s impressive improvement requires a short proof that does not seem to rely on any kind of heavy machinery.

Advertisements

Local Properties that imply Many Distinct Distances

Jacob Fox, Janos Pach, and Andrew Suk just placed this paper on arXiv. The paper seems very nice, but unfortunately for Ben Lund, Frank de Zeeuw, and myself, it contains a result that is almost identical to one that we had but did not yet publish. Instead of sulking alone in the dark, in this post I describe the problem and our result.

JFoxJPachAsuk
Jacob Fox, Janos Pach, and Andrew Suk.

Let \phi(n,k,l)  denote the minimum number of distinct distances that can be determined by a set of n  points {\cal P} \subset {\mathbb R}^2  with the property that any k  points of \cal P  determine at least l  distinct distances. That is, by assuming that the point set satisfies a local property, we wish to conclude the global property of many distinct distances.

For example, the value of \phi(n,3,3)  is the minimum number of distinct distances that are determined by a set of n  points that do not span any isosceles triangles (including degenerate triangles with three collinear vertices). Since no isosceles triangles are allowed, every point determines n-1  distinct distances with the other points of the set, and we thus have \phi(n,3,3) = \Omega(n)  . Erdős observed the following upper bound for \phi(n,3,3)  . Behrend proved that there exists a set A  of positive integers a_1<a_2<\cdots<a_n  , such that no three elements of A  determine an arithmetic progression and that a_n < n2^{O(\sqrt{\log n})}  . Therefore, the point set {\cal P}_1 = \{(a_1,0), (a_2,0),\ldots, (a_n,0)\}  does not span any isosceles triangles. Since {\cal P}_1 \subset {\cal P}_2 = \{(1,0),(2,0),\ldots,(a_n,0) \}  and D({\cal P}_2)< n2^{O(\sqrt{\log n})}  , we have \phi(n,3,3) < n2^{O(\sqrt{\log n})}  .

In the same paper, Erdős derived the more general bound

\phi\left(n,k,\binom{k}{2}-k+3\right) = \Omega(n).

As Fox, Pach, and Suk point out, a result by Sarkozy and Selkow implies the slightly stronger (with \varepsilon  depending on k  )

\phi\left(n,k,\binom{k}{2}-k+4+\log k\right) = \Omega(n^{1+\varepsilon}).

We are now ready to state our result. The result of Fox, Pach, and Suk is identical up to the +5  being replaced with +6  . While there are some similarities between the two proofs, they do not seem to be identical.

Theorem 1. For every even k\ge 6  and \varepsilon>0  , we have

\phi\left(n,k,\binom{k}{2}-k+5\right) = \Omega(n^{8/7-\varepsilon}).

Continue reading

A list of recent papers

Lately I did not have much time to survey the recent developments in the polynomial method / algebraic combinatorial geometry / whatever it is called these days. Hopefully this will change soon, but for now here is a list of papers from the past year that were not discussed in this blog before. I think that these illustrate how active the field currently is (and I did not include several recent results that have been announced but are not available online yet). Feel free to point out other papers which I might have missed.

1. Polynomial partitioning for a set of varieties / Guth. This paper introduces a new type of polynomial partitioning. Instead of defining a partitioning with respect to a point set such that no cell contains a bounded number of points, this partitioning is defined with respect to a set of varieties and satisfies that every cells intersects a bounded number of varieties. It would be interesting to find new applications for such partitionings.

2. On the use of Klein quadric for geometric incidence problems in two dimensions / Rudnev and Selig. Studies the Elekes-Sharir(-Guth-Katz) framework from a somewhat new perspective. The paper generalizes several variants of the framework, bypassing the standard use of symmetry in such cases.

3. On the number of rich lines in truly high dimensional sets / Dvir and Gopi. The paper derives an upper bound for the number of r  -rich lines in {\mathbb C}^d  . For this purpose, Dvir and Gopi combine polynomial partitioning interpolation with a method relying on design matrices. In recent years, this method was used to obtain bounds for various higher dimensional variants of the Sylvester-Gallai problem.

Continue reading

Random Stories Pictures from IPAM – Part 3

We finished our IPAM semester with a workshop at lake arrowhead. You can find our “graduation pictures” at the IPAM facebook page (just don’t look at my horrible picture…). In honor of this amazing semester, here are some pictures that I have from it. If you have other nice pictures, you’re welcome to send them to me and I’ll place them here.

IMG_2186
A farewell party to Micha, just before he was leaving LA.

P1000076
The notorious reading group, trying to get through Harris’ algebraic geometry book.

P1000105
Abdul Basit took us to what according to him is the best Pakistani food that he had outside of Pakistan.

P1000094
Pool party!

Random Stories from IPAM – Part 2

If you are not in Los Angeles but are interested in these topics, you can now view videos of many of the talks that we had here. Talks from the tutorials week can be found here. Talks from the workshop “Combinatorial Geometry Problems at the Algebraic Interface” can be found here. I assume that talks from the workshop “Tools from Algebraic Geometry” will also be available soon.

Landsberg
A talk by Joseph Landsberg.

Another brief update: You might remember that in my previous IPAM post I was excited about a talk by Larry Guth. Not only that you can now watch the video of this talk, but you can also read the paper.

And now for quote of the week:

It is like defining a ham sandwich as “what you have in your lunchbox after taking the apple out”.

                Ben Lund, unsatisfied with a famous textbook’s definition of Grassmannians.

After three weeks without any main events, another workshop begins tomorrow. So more updates will follow.

Recent Results (Feb `14)

In this post I briefly mention several recent papers that are related to the topics of this blog (I might later write more detailed posts about some of these). This is not a comprehensive list, as there are many new relevant papers. Some other recent results can be found in the list of papers that were accepted to SoCG 2014, though I am not mentioning papers that still do not have a full version available online. Soon I will also add these to the related papers page.

1. Polynomials vanishing on grids: The Elekes-Rónyai problem revisited / Raz, Sharir, and Solymosi. In my previous post, about the partial Elekes-Sharir framework, I mentioned the existence of a couple of unpublished results that apply this technique to problems that do not directly involve distinct distances. This is the first of these papers, and the main result in it is the following improvement of a special case of recent result by Elekes and Szabó.

Theorem 1 (Raz, Sharir, and Solymosi). Consider a grid A\times B\times C \subset {\mathbb R}^3  , where |A|=|B|=|C|=n  , and a polynomial f\in{\mathbb R}[x,y,z]  which is of the form z=g(x,y)  . Then if f  vanishes on \Omega(n^{11/6})  points of the grid, it must be either of the form f=h(\varphi(x)+\psi(y))  or the form f=h(\varphi(x)\cdot\psi(y))  , for h,\varphi,\psi \in {\mathbb R}[x]  .

This appears to be a rather strong result with various applications, including subsuming several previous results that were obtained by applying the partial Elekes-Sharir framework. The paper by Elekes and Szabó is significantly more general in the sense that it applies to any f  (not just of the form z=g(x,y)  ), to grids in the complex space, and to more general scenarios in higher dimensions. However, it is not clear to me (or to other people that I have asked) what exactly are the bounds that were obtained in it (that is, compared to \Omega(n^{11/6})  ), which seem to also depend on the degree of f  .

2. Distinct volume subsets / Conlon, Fox, Gasarch, Harris, Ulrich, and Zbarsky. I already had a post about a previous version of this paper (which back then I found through google scholar and by mistake thought that it was public). In one rather imprecise sentence: the paper shows that for every set \cal P  of n  points in {\mathbb R}^d  and for every 1 \le a \le d  , there exists a large subset {\cal P}' \subset {\cal P}  , such the points of {\cal P}'  do not span two a  -dimensional simplices with the same volume (hence the name Distinct volume subsets). The main results have remained more or less the same and you can find more details about them in my original post. However, the new (and official!) version of the paper is significantly shorter. As William Gasarch was describing it to me, the new version has “cleaner defintions, cleaner proofs, and more precise results.”

3. Algebraic combinatorial geometry: the polynomial method in arithmetic combinatorics, incidence combinatorics, and number theory / Tao. This paper is a survey and is already three months old, but I think that it is worth mentioning. The survey discusses recent techniques such as polynomial partitioning, the existence of bounded-degree polynomials that vanish over a given point set, etc., but also other topics such as Alon’s combinatorial nullstellensatz.

In the survey, Tao dubs this (sub-)field as algebraic combinatorial geometry, so perhaps I should start saying that this is a blog that focuses on algebraic combinatorial geometry. I am quite happy about Tao uniting these various techniques under one roof and naming it. I hope that this would help making the field more known and to push it forward.