Nathan Rubin Improved the Bound for Planar Weak ε-Nets and Other News From Ein-Gedi

Combinatorics and more 2018-04-05

I just came back from a splendid visit to Singapore and Vietnam and I will write about it later. While I was away, Nathan Rubin organized a lovely conference on topics closed to my heart ERC Workshop: Geometric Transversals and Epsilon-Nets with many interesting lectures. Nathan himself announced a great result with new upper bounds for planar weak ε-nets. In 2007 I wrote a guest post (my first ever blog post) on the topic on Terry Tao’s blog. The next section is taken from that old post with reference to one additional result from 2008.

Weak ε-Nets

Definition: Let $X \subset {\Bbb R}^d$ be a finite set of points, and let $0 < \epsilon < 1$ . We say that a finite set $Y \subset {\Bbb R}^d$ is a weak $\epsilon$ -net for X (with respect to convex bodies) if, whenever B is a convex body which is large in the sense that $|B \cap X| > \epsilon |X|$ , then B contains at least one point of Y. (If Y is contained in X, we say that Y is a strong $\epsilon$ -net for X with respect to convex bodies.)

let $f(\epsilon,d)$ be the least number such that every finite set X possesses at least one weak $\epsilon$ -net for X with respect to convex bodies of cardinality at most $f(\epsilon,d)$ . (One can also replace the finite set X with an arbitrary probability measure; the two formulations are equivalent.) Informally, f is the least number of “guards” one needs to place to prevent a convex body from covering more than $\epsilon$ of any given territory.

A central problem in discrete geometry is:

Problem: For fixed d, what is the correct rate of growth of f as $\epsilon \to 0$ ?

It is already non-trivial (and somewhat surprising) that $f(\epsilon,d)$ is even finite. This fact was first shown by Alon, Bárány, Füredi, and Kleitman (the planar case was achieved earlier by Bárány, Füredi, and Lovász), who established a bound of the form $f(\epsilon,d) = O_d( 1/\epsilon^{d+1})$ ; this was later improved to $O_d(\frac{1}{\epsilon^d} \log^{O_d(1)} \frac{1}{\epsilon} )$ by Chazelle, Edelsbrunner, Grigni, Guibas, Sharir, and Welzl. In the other direction, the best lower bound was for many years $c(d)/\epsilon$ for some positive c(d); it was shown by Matousek that c(d) grows at least as fast as $e^{c\sqrt{d}}$ for some absolute constant c. In 2008 Bukh, Matousek, and Nivasch proved that $f(\epsilon,d) \ge (1/\epsilon) (\log (1/ \epsilon)^{d-1}$ .

Nathan Rubin’s new theorem

In the plane the state of our knowledge was that (up to constants) for every $\delta >0$ ) $(1/\epsilon )\log (1/\epsilon) \le f(2,\epsilon) \le (1/\epsilon)^{2+\delta}$ . The new dramatic breakthrough is

Theorem (Nathan Rubin, 2018): $f(2,\epsilon) \le (1/\epsilon)^{3/2+\delta}$ .

I hope the paper will be arxived in the next few months.

Other results from Ein-Gedi

Here is a page with the titles and abstracts of the lectures. A lot of very interesting advancements on Helly-type theorems, transversals, geometric-Ramsey, topological methods and other topics. Let me briefly mention one direction.

Improved (p,q)-theorems

Weak $\epsilon$ -nets play an important role in the proof by Alon and Kleitman of the Hadwiger-Debrunner conjecture. The proof is so nice that I could not resist the temptation to present and discuss it in two comments (1,2) to my old 2007 posts.

Theorem (Alon and Kleitman): For every integers $p,q$ and $d$ , $p \ge q \ge d+1$ , there is a function $M(p,q;d)$ such that the following is true:

Every finite family $\cal K$ of convex sets in ${\Bbb R}^d$ with the property that among every $p$ sets in the family there are $q$ with non empty intersection can be divided to at most $M(p,q;d)$ intersecting subfamilies.

Dramatic improvements of the bounds for $M(p,q,d)$ were achieved in a 2015 paper Improved bounds on the Hadwiger-Debrunner numbers by Chaya Keler, Shakhar Smorodinsky, and Gabor Tardos. This have led to further improvements and related results that Shakhar and Chaya talked about in the meeting.

Other results around weak ε-Nets

There were various other developments regarding weak ε-Nets andrelated notions that occured since my 2007 post and the result of Buck, Matousek, and Nivasch in 2008, and probably I am not aware of all of them (or even forgot some). Of course, comments about related results are most welcome in the comment section. Here are links to a lecture by Noga Alon: 48 minutes on strong and weak epsilon nets (Part 1, Part 2). Let me mention just two beautiful recent developments: A paper On weak ε-nets and the Radon number by Moran and Yehudayoff gives a simple proof for their finiteness in a very abstract setting. A paper by Har-Peled and Jones How to Net a Convex Shape studies interesting weaker notions. A weaker notion of weak epsilon nets is described in the work by Bukh and Nivash in Nivash’s Ein Gedi abstract.