My Copy of Branko Grünbaum’s Convex Polytopes

Branko Grünbaum is my academic grandfather (see this highly entertaining post for a picture representing five academic generations). Gunter Ziegler just wrote a beautiful article in the Notices of the AMS on Branko Grunbaum’s  classic book “Convex Polytopes”, so this is an opportunity to tell the story of my copy. The book was written with the cooperation of Victor Klee, Micha Perles (my Ph. D supervisor) and Geoffrey Shephard. Since the late 70s the book was out of print and it was extremely difficult to get a copy.

In 1983 I was a postdoc in MIT and there was a lovely group of young combinatorialists around. At MIT, Noga Alon, and I, as well as  Ian Goulden and a few others were postdocs,  Jeff Kahn, Paul Seymour, Ira Gessel, and Anders Björner were junior faculty, Gunter Ziegler, Mark Haiman, Francesco Brenti, and Peter Shor were among the graduate students. There were many computer scientists with interest in combinatorics and at Northeastern there were two young faculty members, Marge Bayer and Dom (Dominique) de Caen working in combinatorics, and an algebraic geometer Jonathan Fine who also became interested in combinatorics.

One day, Dom de Caen saw me and told me that some months earlier he had managed to find a copy of “Convex polytopes” in a used book store and bought it for 10 dollars. He said that he knew how rare the book was and how hard it was to get it, but decided to give it to me  since I would make  better use of it working in this special area.

 

 

In 2003, after several years of work, a second edition was published which contained the original text and some additional material prepared by a fresh team of young researchers: Volker Kaibel, Victor Klee, and Gunter Ziegler. This was really great. I bought a copy and had the idea to send it to Dom as a form of gratitude for his previous gesture of kindness.  So I tried to find his address over the Internet. I was sad to learn that Dom had passed away in 2002. You can read about Dom’s mathematics in this paper by  Edwin R. Van Dam,  The combinatorics of Dom de Caen.

Advertisements
Posted in Combinatorics, Convex polytopes, Nostalgia | Tagged , , | 3 Comments

Cohen, Haeupler, and Schulman: Explicit Binary Tree-Codes & Cancellations

The high-dimensional conference in Jerusalem is running with many exciting talks (and they are videotaped), and today in Tel Aviv there is a conference on Optimization and Discrete Geometry : Theory and Practice.

Today in Jerusalem, Leonard Schulman talked (video available!) about a  recent breakthrough by  Gil Cohen, Bernhard Haeupler, and Leonard Schulman in the recent paper Explicit Binary Tree Codes with Polylogarithmic Size Alphabet.

Tree codes

Tree codes are extremely important objects invented by Leonard Schulman in 1992-1996. You can read about it in Wigderson’s book  Mathematics and Computation  (see also this post) in a whole section about  Error-correction of interactive communication, a theory pioneered by Leonard. Finding explicit good (linear distance, finite alphabet) tree codes is a very important problem.

(From the introduction of the new paper) “A tree code consists of a complete rooted binary tree (either infinite or of finite depth n) in which each edge is labeled by a symbol from an alphabet \Sigma . There is a natural one-to-one mapping assigning each binary string s to a path starting at the root, where s simply indicates which child is taken in each of the steps. For a tree code, such a path naturally maps to a string over the alphabet \Sigma, which is formed by concatenating the symbols along the path. This way a tree code T encodes any binary string s into an equally long string T(s) over \Sigma. This encoding has an online characteristic because the encoding of any prefix does not depend on later symbols. In particular, any two distinct strings that agree in their first k symbols also have encodings that agree in their first k symbols. A tree code is said to achieve distance  \delta \ge 0 if the encodings of any two strings differ in at least a \delta-fraction of the positions after their first disagreement. The rate of a tree code is 1/\log _2 (\Sigma ). A tree code is said to be asymptotically good if it achieves both constant distance \delta >0  and a constant rate, namely, the alphabet size is O(1).”

The abstract:

“This paper makes progress on the problem of explicitly constructing a binary tree code with constant distance and constant alphabet size.

For every constant 1 we give an explicit binary tree code with distance  and alphabet size (\log n)^{O(1)}, where n is the depth of the tree. This is the first improvement over a two-decade-old construction that has an exponentially larger alphabet of size n^{O(1)}.

As part of the analysis, we prove a bound on the number of positive integer roots a real polynomial can have in terms of its sparsity with respect to the Newton basis – a result of independent interest.”

Problems on Exponential sums

A few years ago Cris Moore and Leonard Schulman proposed an explicit constructions for good tree codes in the paper Tree codes and a conjecture on exponential sums. The construction depends on still open conjectures on new types of exponential sums.

A paper by Leonard and me on polynomials with massive cancellations.

So let me use this opportunity to advertize a paper by Leonard and me Quasi-random multilinear polynomials which was just accepted for publication in the Israel Journal of Mathematics. Unexpected cancellation is always a very interesting phenomenon that we cherish and wish to understand. For example, we expect that the sum of the Mobius function for the first n integers cancels almost like that of a random walk. Depending on the meaning of “almost” this is the (known) prime number theorem, the (conjectured) Riemann hypothesis, or simply false, respectively.

A little less famous example  (which I personally like) is the paper by Nikola Djokic  an upper bound on the sum of signs of permutations with a condition on their prefix sets solving a problem by J. Feldman, H. Knorrer, and E. Trubowitz.

Our starting point is the determinant: It is a polynomial of degree n of n^2 variables and no matter what \pm 1 values you assign to the variables you have a massive cancellation of almost a random-walk type. There are n! terms and for any assignment the value is smaller than n^{n/2} which is (n!)^{1/2+o(1)}.  We were interested in the question of finding other such polynomials.

Posted in Combinatorics, Computer Science and Optimization, Open problems | Tagged , , , | 1 Comment

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…

Posted in Combinatorics, Test your intuition | Tagged | 6 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 , , | 8 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. (April 21) A great blog post (French) on Automath.

(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 , | 10 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 , | 2 Comments

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