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.
Definition: Let be a finite set of points, and let . We say that a finite set is a weak -net for X (with respect to convex bodies) if, whenever B is a convex body which is large in the sense that , then B contains at least one point of Y. (If Y is contained in X, we say that Y is a strong -net for X with respect to convex bodies.)
let be the least number such that every finite set X possesses at least one weak -net for X with respect to convex bodies of cardinality at most . (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 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 ?
It is already non-trivial (and somewhat surprising) that 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 ; this was later improved to by Chazelle, Edelsbrunner, Grigni, Guibas, Sharir, and Welzl. In the other direction, the best lower bound was for many years for some positive c(d); it was shown by Matousek that c(d) grows at least as fast as for some absolute constant c. In 2008 Bukh, Matousek, and Nivasch proved that .
Nathan Rubin’s new theorem
In the plane the state of our knowledge was that (up to constants) for every ) . The new dramatic breakthrough is
Theorem (Nathan Rubin, 2018): .
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.
Weak -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 and , , there is a function such that the following is true:
Every finite family of convex sets in with the property that among every sets in the family there are with non empty intersection can be divided to at most intersecting subfamilies.
Dramatic improvements of the bounds for 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.