The k-set problem

The k  -set problem is a classic open problem in Combinatorial Geometry, which is considered similar in spirit to incidence problems and to distance problems. While in recent years algebraic techniques led to significant progress in incidence and distance problems, so far none of the new methods were applied to the k  -set problem. This post briefly introduces the problem, and describes a way of reducing it to an incidence problem. I hope that it will get someone to think of the k  -set problem in an algebraic context and maybe come up with some new observations.

Let {\cal P}  be a set of n  points in {\mathbb R}^2  , and let 1\le k\le n/2  be an integer. A k  -set of {\cal P}  is a subset {\cal P}'\subset {\cal P}  of k  points such that there exists a line that separates {\cal P}'  from {\cal P}\setminus{\cal P}'  . That is, {\cal P}'  is on one open half-plane defined by the line, while {\cal P}\setminus{\cal P}'  is on the other half-plane. The following figure depicts two 5-sets of a set of 12 points.

5sets.eps

The k  -set problem asks for the maximum number of k  -sets that a set of n  -points in {\mathbb R}^2  can have. As a first silly example, note that the maximum number of 1-sets is exactly n  . It is not difficult to show that we may assume that no three points are collinear (specifically, perturbing the point set cannot significantly decrease the number of k  -sets).

The number of subsets of k  points of {\cal P}  is \Theta(n^k)  , so this is a straightforward upper bound for the maximum number of k  sets. However, we can easily obtain a significantly stronger upper bound. Consider a k  -set {\cal P}'\subset{\cal P}  that is separated by a line \ell  . We translate \ell  until it is incident to a point p\in {\cal P}'  and then rotate \ell  around p  until it is incident to a second point of {\cal P}  (not necessarily in {\cal P}'  ). For example, see the figure below. Thus, to find all of the k  -sets of {\cal P}  it suffices to consider every line that is incident to two points of {\cal P}  . Since there are O(n^2)  such lines, this is also an upper bound for the number of k  -sets.

kSetLineChange.eps

Continue reading

A First Draft of the Book “Incidence Theory”

You might have noticed that I did not post anything new for quite a while. The past months were unusually busy for me, due to personal reasons such as having my first child born(!), being on the job market, and several other things. I hope to return to my regular posting frequency around July.

The purpose of this post is to announce that I just uploaded the first draft of my book “Incidence Theory”. This book is about our current understanding of incidences (with a focus on the polynomial method), and their applications in other fields. I am trying to achieve two goals in this book: To have a clear and basic introduction of this subfield, while also creating a repository of results and techniques which may be used as a reference to experts. The current draft already contains several folklore results that I have not seen written before. It contains only the first seven chapters. I predict that the final version would contain about 15 chapters, and plan to gradually release the remaining ones.

Comments would be very appreciated, preferably by email. These can point out mistakes, typos, unclear formulations, suggestions for style changes, additional topics, simpler arguments, exercises, or anything else that might help improve the draft. The acknowledgements section is way too short. Please help me to extend it!

Additive Energy of Real Point Sets

Over the years, more and more interactions between Discrete Geometry and Additive Combinatorics are being exposed. These include results such as the Green–Tao ordinary lines theorem and Solymosi’s sum-product bound. One reason for this connection is that both fields study the structure and symmetries of various objects (such as sets of points or subsets of additive groups). In this post I will discuss one of the simplest connections between the two fields — studying the additive energy of a set of points in a real space {\mathbb R}^d  . The main goal of the post is to present two open problems that involve the additive energy of such sets. I heard one of these problems from Nets Katz and the other from Ciprian Demeter. In future posts we might discuss more involved interactions between the two fields.

demeterckatz
Ciprian Demeter and Nets Katz.

Continue reading

(More) Local Properties that imply Many Distinct Distances

Last year I wrote a post about a distinct distances problem that involves local properties of the point set. Specifically, let \phi(n,k,l)  denote the minimum number of distinct distances that can be determined by a set {\cal P} \subset {\mathbb R}^2  of n  points, such 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 more details and examples, see the original post.

A while ago I noticed another nice bound for this set of problems. Unfortunately the proof is very simple, which prevents it from being published in a “decent” journal. I’ve been trying to push it further, so far without success. Perhaps someone else would see how this idea can be extended.

As discussed in the previous post, Fox, Pach, and Suk proved that for every k\ge 6  and \varepsilon>0  , we have

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

A simple argument shows that for every k\ge 4  we have

\phi\left(n,k,\binom{k}{2}-\lfloor k/2 \rfloor +2\right) = \Omega(n^2).

Our interest in this post lies in between these two bounds. That is, what happens between the values \binom{k}{2}-k+6  and \binom{k}{2}- k/2 +2  . I am only aware of one previous result in thie range: Erdős and Gyárfás showed that \phi\left(n,k,\binom{k}{2}-\lfloor k/2 \rfloor +1\right) = \Omega(n^{4/3})  . We will now prove a stronger result.

Theorem 1. For every k\ge 8  that is divisible by four, we have

\phi\left(n,k,\binom{k}{2}- 3k/4 +3\right) = \Omega_k(n^{4/3}).

Continue reading

The Sum-Product Bound of Konyagin and Shkredov

In Solymosi’s famous 2009 paper, he proved that every finite set A\subset {\mathbb R}  satisfies

|A+A||AA| = \Omega\left(|A|^{4/3}/\log^{1/3}|A|\right).

In the past couple of years, Konyagin and Shkredov published two papers that extend Solymosi’s argument, obtaining a slightly stronger sum-product bound (one and two). These papers derive several additional results, and apply a variety of tools. I just uploaded to this blog my own exposition to the sum-product proof of Konyagin and Shkredov (a link can also be found in the pdf files page). This exposition ignores the additional results that are in the two papers, and tries to explain in detail every step that is part of the sum-product proof. In this aspect, the document would hopefully also fit beginners. As usual, I’m happy to receive any comments and corrections.

konyaginIlya-00
Ilya Shkredov and Sergei Konyagin.

Additive Combinatorics Lecture Notes (part 2)

I finished my additive combinatorics class, and placed all of the lecture notes in the pdf files page. This quarter was rather short and I did not get to do several topics I had in mind. Perhaps I’ll add notes for some of these at some point. For now, let me just list the chapters that did not appear in the previous post.

  • Chapter 4 is about arithmetic progressions in dense sets. It includes Behrend’s construction, Meshulam’s theorem, and Roth’s theorem. Due to the recent developments, Meshulam’s theorem already seems somewhat outdated…
  • Chapter 5 consists of Sander’s proof of the quasi-polynomial Freiman-Ruzsa theorem in {\mathbb F}_2^n  (following Lovett’s presentation). This includes proving a special case of the probabilistic technique of Croot and Sisask.
  • Chapter 6 presents the technique of relying on the third moment energy. It then uses this technique to study convex sets. I hope to also add a variant of the Balog-Szemerédi-Gowers theorem.

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.