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.

I forgot to add polls…

Advertisements
Posted in Combinatorics, Test your intuition | Tagged | 3 Comments

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 | Tagged , , | 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.

Aubrey de Grey has constructed  a unit distance graph with 1567 vertices which is 5-chromatic!

 

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.

Posted in Combinatorics, Geometry, Open problems, Updates | Tagged , | 9 Comments

Conference on High Dimensional Combinatorics, April 22-26 2018

Conference on High Dimensional Combinatorics

Conference home-page

Dates: April 22-26, 2018

Place: Israel Institute for Advanced Studies, The Hebrew University of Jerusalem

Organizers: Alex Lubotzky, Tali Kaufman and Oren Becker

Registration form: click here

Registration deadline: April 13, 2018

Combinatorics in general and the theory of expander graphs in particular, have been fruitful areas of interaction between pure and applied mathematics. In recent years a “high dimensional” theory has emerged. This theory, aside from its intellectual interest, also has great potential for various applications in mathematics and computer science. This theory calls for a collaboration of experts in combinatorics, topology, geometry, group theory and computer science.

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
Posted in Combinatorics, Computer Science and Optimization, Conferences | Tagged , | Leave a comment

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 dp \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.

Posted in Combinatorics | Tagged , | Leave a comment

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.)

Background (a little more than needed)

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 ks 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.

 

Posted in Combinatorics, Mathematics over the Internet, Open problems | Tagged , , , | 11 Comments

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?

Answers are most welcome.

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.

 

Posted in Combinatorics | Tagged , | Leave a comment