## Test Your Intuition (34): Tiling high dimensional spaces with two-dimensional tiles.

A tile $T$ is a finite subset of $\mathbb Z^d$. We can ask if $\mathbb Z^d$ can or cannot be partitioned into copies of $T$. If  $\mathbb Z^d$ can be partitioned into copies of $T$ we say that $T$ tiles $\mathbb Z^d$.

Here is a simpe example. Let $T$ consists of 24 points of the 5 by 5 planar grid minus the center point. $T$ cannot tile $\mathbb Z^2$.

Test your intuition: Does $T$ tiles $\mathbb Z^d$ for some $d>2$?

If you prefer you can think about the simpler case of $T_0$ consisting of eight points: the 3 by 3 grid minus the center.

## Coloring Problems for Arrangements of Circles (and Pseudocircles)

To supplement and celebrate Aubrey de Grey’s result here are

## Eight problems on coloring circles

A) Consider a finite family of unit circles. What is the minimum number of colors needed to color the circles so that tangent circles are colored with different colors?

This is the question about the chromatic number of the plane. (Or the maximum chromatic number of planar unit-distance graphs.) By the Aubrey de Grey’s result the answer is 5, 6, or 7.

B) Consider a finite family of non-overlapping unit circles. What is the minimum number of colors needed to color the circles so that tangent circles are colored with different colors?

Now we talk about planar unit-distance graphs where the distance between every pair of points is at least one. Those are also called Penny graphs. The answer is four.

C) Consider a finite family of pairwise intersecting unit circles. What is the minimum number of colors needed to color the circles so that tangent circles are colored with different colors? Continue reading

Posted in Combinatorics, Geometry, Open problems | | 5 Comments

## Aubrey de Grey: The chromatic number of the plane is at least 5

A major progress on an old standing beautiful problem. Aubrey de Grey proved that the chromatic number of the plane is at least 5. (I first heard about it from Alon Amit.)

The Hadwiger–Nelson problem asks for the minimum number of colors required to color the plane such that no two points at distance one from each other have the same color. The answer is referred to as the chromatic number of the plane. The problem was posed in 1950 by Edward Nelson, and related results already appeared in a paper by Hugo Hadwiger from 1945. Untill recently it was known that the answer can be 4,5,6 or 7. The Moser spindle is a simple example of a unit-distance graph with chromatic number 4, and there is a simple coloring of the plane, found by Isbell, based on the hexagonal packing with 7 colors so that no color contains a pair of points of distance 1.

Updates: Aubrey de Grey has made now a polymath proposal over the polymath blog aimed at finding simpler constructions, namely constructions with a smaller number of vertices, or where the computerized part of the proof is simpler. Of course, this project may lead to independent verification of the result, and perhaps even insights for what is needed to replace ‘5’ with ‘6’. Noam Elkies independently proposed over MathOverflow a polymath project following Aubrey de Grey’s paper. (April 14) Dustin Mixon and Aubrey de Grey have launched Polymath16 over at Dustin’s blog. The project is devoted to the chromatic number of the plane (Wikipage) following Aubrey de Grey’s example showing that the chromatic number of the plane is at least 5.

Here is an earlier Google+ post by Terry Tao and an earlier blogpost on the new result by Jordan Ellenberg proposing to use the polynomial method to tackle the upper bound. A blog post reporting on independent verification of some of the new results is over Dustin G. Mixon’s blog  Short, Fat Matrices. A post over Shtetl Optimized describes the new development along with another important development on quantum computation. Let me also mention two related old posts over Lipton and Regan’s blog (one, two). (April 19) An excellent article on Quanta Magazine by Evelyn Lamb.

(From Wikipedea: A seven-coloring of the plane, and a four-chromatic unit distance graph in the plane (the Moser spindle), providing upper and lower bounds for the Hadwiger–Nelson problem.) Below, two figures from Aubret de Grey’s paper.

Let me also mention the related Rosenfeld’s problem discussed in this post: Let G be the graph whose vertices are points in the plane and two vertices form an edge if their distance is an odd integer. Is the chromatic number of this graph finite?

These and related problems are discussed also in my survey article: Some old and new problems in combinatorial geometry I: Around Borsuk’s problem.

## Conference on High Dimensional Combinatorics

Conference home-page

## Speakers include:

 David Conlon University of Oxford Michael Farber Queen Mary, University of London Howard Garland* Yale University Lev Glebsky Universidad Autónoma de San Luis Potosí Misha Gromov* IHES Venkatesan Guruswami Carnegie Mellon University Ming-Hsuan Kang National Chiao Tung University Daniela Kühn University of Birmingham James Lee University of Washington Winnie Li Pennsylvania State University Shachar Lovett UC San Diego Roy Meshulam Technion Deryk Osthus University of Birmingham János Pach NYU Peter Sarnak IAS, Princeton Leonard Schulman Caltech Uli Wagner IST Shmuel Weinberger University of Chicago Avi Wigderson IAS, Princeton Gilles Zémor Université de Bordeaux

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

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.

Posted in Combinatorics, Convexity, Geometry, Open problems | Tagged | 1 Comment

## A Wonderful Paper by Igor Pak: Complexity Problems in Enumerative Combinatorics

Greetings from Sa Pa in the very north of Vietnam. Let me recommend a  great thought-provoking paper by Igor Pak:  Complexity problems in enumerative combinatorics.

As Igor wrote on his blog: Well, I finally finished my ICM paper. It’s only 30 pp, but it took many sleepless nights to write and maybe about 10 years to understand what exactly do I want to say.

## Frankl’s Conjecture for Large Families: Ilan Karpas’ Proof

Frankl’s conjecture asserts that a for every finite family of of finite sets that is closed under union, there is an element that belongs to at least half the sets in the family. We mentioned the problem in our very first post, and Tim Gowers ran polymath 11 in attempt to solve it (first post, wikipage). See also this post over GLL and this post.

Here, I want to show Ilan Karpas’ proof (that we mentioned in this post) that the conjecture is correct for “large” families, namely, for families of at least $2^{n-1}$ subsets of $[n]$. Karpas’ proof is taken from his paper  Two results on union closed families.

Can Fourier methods solve Frankl’s conjecture? I hope we could have a small discussion about it and related matters, and, in any case, I myself have some comments that I will leave to the comment section.

## The theorem

Theorem (Karpas): If $B$ is a union closed family of subsets of $[n]$, and $|B| \ge 2^{n-1}$ then there exists an element $k \in [n]$ such that $|\{S \in B: k \in S\}| \ge |B|/2$.

Theorem 2 (Karpas): If $A$ is a family of subsets of $[n]$, $|A|\le 2^{n-1}$ with the property

(*) If $S\in A$ and $a,b \in S$, $a\ne b$ then either $S \backslash \{a\}\in A$ or $S \backslash \{b\}\in A$.

Then there exists an element $k \in [n]$ such that $|\{S \in A: k \in S\}| \le |A|/2$.

The implication from Theorem 2 to Theorem 1 is very easy. If $B$ is a union-closed family and $A$ is the complement of $B$, then $B$ satisfies (*). (Otherwise,  $S \backslash \{a\}\in B$ and $S \backslash \{b\}\in B$ and their union $S$ must be in $B$. If $B$ has at least $2^{n-1}$ elements then $A$ has at most $2^{n-1}$ elements. If $|\{S \in A: k \in S\}| \le |A|/2$, then $|\{S \in B: k \in S\}| \ge |B|/2$. We note that Condition (*) is weaker than the assertion that $A$ is union closed and indeed the assertion of Theorem 2 is sharp do not hold when $|A|$ is large. (See remark below.)

## Edge boundary/influence terminology

For a family $A$ of subsets of $[n]$ its edge-boundary is defined by $E(A,\bar A)= \{(S,T) d(S,T)=1, S \in A, T \notin A\}$

The total influence of $A$ is defined by $I(A) = \frac {1}{2^{n-1}}|E(A,\bar A)|$

### Up and down edge boundaries:

$E^-(A,\bar A)= \{(S,T) : d(S,T)=1, S \in A, T \notin A, T \subset S \}$

$E^+(A,\bar A)= \{(S,T) : d(S,T)=1, S \in A, T \notin A, S \subset T \}$

$I^+(A) =2^{-(n-1)}|E^+(A,\bar A)|$

$I^-(A) =2^{-(n-1})|E^-(A,\bar A)|$

## Directional boundaries and individual influences

We now define:

$I_k^-(A)= 2^{-(n-1)}|\{S \in A, k \in S, S \backslash\{k\} \notin A \}|$,

$I_k^+(A)=2^{-(n-1)}|\{S \in A, k \notin S, S \cup \{k\} \notin A \}|$,

The influence of $k$ on A is defined by:

$I_k(A)=I_k^+(A)+I_k^-(A)$

Note that the assertion for Frankl’s conjecture is equivalent to: For every union-closed family $B$ there is $k$ such that $I_k^-(B) \ge I_k^+(B)$. Equivalently for every family $A$ whose complement is union-closed (such families are called “simply rooted”) there is $k$ such that $I_k^+(A) \le I_k^-(A)$.

## Sensitivity/Pivotality

Now, fix a family $A$ of subsets of $[n]$, for $S \in A$, $h_k(S) = 1$, if $S \delta \{k\}\not in A$ and $h_k(S) = 0$ otherwise. $h^+_k(S)=1$ if $k \in S$ and $h_k(S) = 1$. (In other words, $k \in S$ and $S \backslash \{k\}\notin A$.) $h^-_k(S)=1$ if $k \notin S$ and $h_k(S) = 1$. (In other words, $k \notin S$, and $S \cup \{k\}\notin A$.) Define also $h(S) = h_1(S)+h_2(S)+\cdots h_n(S),$ $h^+(S) = h^+_1(S)+h^+_2(S)+\cdots + h^+_n(S),$ $h^-(S) = h^-_1(S)+h^-_2(S)+\cdots + h^-_n(S).$

Note that $I_k^+(A)=2^{-(n-1)}\sum_{S \in A} h_k^+(S)$, and similarly for other types of influences.

## Fourier

Let $f:\{0,1\}^n \to \{-1,1\}$ be a Boolean function defined as follows: $f(x)=-1$ if $x$ represents a set in $A$, and $f(x)=1$, otherwise.

We write $\hat A(S)=\hat f(S)$.

It is well known and easy to see that $\hat A(\{k\})=I^+_k(A)-I^-_k(A)$.

Parseval’s formula gives $\sum \hat A^2(S)=1$. It follows easily from Parseval’s formula that $I_k(A)=\sum \{\hat A^2(S):k \in S\},$  and hence $I(A)=\sum \hat A^2(S)|S|.$

## The proof:

We write $|A|=(1/2-\delta) 2^n$.

Our assumption (*) on $A$ is that if $S\in A$ and $a,b \in S$, $a\ne b$ then either $S \backslash \{a\}\in A$ or $S \backslash \{b\}\in A$. In other words $h^+(S) \le 1$ for every $S \in A$. This implies that

(1) $I^+(A) \le 2^{-(n-1)}|A|=(1-2\delta )$.

We assume that Frankl’s conjecture is false namely that $\hat I^+_k(A) > I^-_k(A)$, for every $k$, or equivalently that

(2)  $I_k^+(A)- I^-_k(A) = \hat A(\{k\}) > 0$, $k=1,2,\dots ,n$.

Summing over all $k$s it follows that $I^-(A) < I^+(A)$ hence

(3) $I(A) < 2I^+(A) \le 2-4\delta$.

From $I(A)=\sum \hat A^2(S)|S|,$ it follows that

(4)  $I(A) \ge 2 - \sum\hat A^2(\{k\}) - 2\hat A^2 (\emptyset )$.

Note that

(5) $\hat A^2(\emptyset )=4\delta^2$

But

(6) $\sum \hat A^2(\{k\}) \le \sum \hat A (\{k\}) = I^+(A)-I^-(A)$

Combining (4,5,6)  we get

$I^+(A)+I^-(A) \ge 2 - I^+(A)-I^-(A) - 4(\delta^2)$, or

(7) $2I^+(A) \ge 2-8\delta^2$.

(1) and (7) gives $1-2\delta >1-4\delta^2$, a contradiction.

## Test your intuition 33: Why is the density of any packing of unit balls decay exponentially with the dimension?

Test your intuition: What is the simplest explanation you can give to the fact that the density of every packing of unit balls in $R^d$ is exponentially small in $d$?

Of course, understanding the asymptotic behavior of the density $\rho_d$ of densest packing of unit spheres in $R^d$ is a central  problem in geometry. It is a long standing hope (perhaps naïve) that algebraic-geometry codes will eventually lead to examples showing that $\rho_d \ge (2-\delta)^{-d}$ giving an exponential improvement of Minkowsky’s 1905 bound.  (For more on sphere packing asymptotically and in dimensions 8 and 24 see this post.)

The result by Serge Vlăduţ from the previous post can be seen (optimistically) as a step in the direction of exponential improvement to Minkowski’s bound.

Posted in Combinatorics, Geometry, Test your intuition | Tagged , | 4 Comments

## Serge Vlăduţ : Lattices with exponentially large kissing numbers

(I thank Avi Wigderson for telling me about it.) Serge Vlăduţ just arxived a paper with examples of lattices in $R^n$ such that the kissing number is exponential in $n$. The existence of such a lattice is a very old open problem and the best record was an example where the kissing number is $n^{\log n}$. (This is based on a 1959 construction of Barnes and Wall and can be found in the famous book by Conway and Sloane.) Noga Alon found in 1997 collections of spheres so that each one touches subexponentially many others. Vlăduţ’s result is very exciting!

A crucial step was a result by Ashikhmin,  Barg, and Vlăduţ from 2001 showing that certain algebraic-geometry binary linear codes have exponentially many minimal weight vectors. (This result disproved a conjecture by Nati Linial and me.) This follows by applying in a very clever way early 80s constructions going back to Bos, Conway, Sloane and Barnes and Sloane, and this requires some subtle selection of the AG-codes that can be used. To quote the author: “In order to apply Constuctions D and E we need specific good curves (the curves in the Garcia Stichtenoth towers do not perfectly match our construction) and some Drinfeld modular curves  perfectly suit our purposes.”

These lines of ideas and appropriate AG-codes look to me the most promising avenue towards exponential lower bound for the Borsuk problem. (See, e.g.,  this paper and this post) We need for that purpose AG codes X where the maximum weight occurs exponentially often (this need not be difficult) and that every subset of vectors that misses the maximum distance is exponentially smaller than |X|.

Posted in Combinatorics, Geometry | Tagged | 4 Comments

## Peter Keevash and Eoin Long: Forbidden vector-valued intersections

Peter Keevash and Eoin Long arxived some time ago a very nice paper:  Forbidden vector-valued intersections, which settled a problem that was first posed here on the blog. Here is the abstract.

We solve a generalised form of a conjecture of Kalai motivated by attempts to improve the bounds for Borsuk’s problem. The conjecture can be roughly understood as asking for an analogue of the Frankl-Rödl forbidden intersection theorem in which set intersections are vector-valued. We discover that the vector world is richer in surprising ways: in particular, Kalai’s conjecture is false, but we prove a corrected statement that is essentially best possible, and applies to a considerably more general setting. Our methods include the use of maximum entropy measures, VC-dimension, Dependent Random Choice and a new correlation inequality for product measures.

Actually, the original motivation for the problem was related to the cap-set problem. (Item 19 in the third post on the cap-set problem and the Frankl-Rodl’s theorem).  In 2009 I wrote three posts (ABC) with some ideas on connections between the cap-set problem and Frankl-Wilson/Frankl-Rodl’s theorem. The first post also dicusses various ways in which Frankl-Rodl’s theorem is more general than Frankl-Wilson.

Other related posts and papers:  Frankl-Wilson theorem; A 2014 paper by Keevash and Long Frankl-Rödl type theorems for codes and permutations;  Posts (I, II) on the startling solution of the cap-set prolems following the works of Croot, Lev, Pach, Ellenberg, and Gijswijt.