Some Mathematical Puzzles that I encountered during my career

Recently, I gave some lectures based on a general-audience personal tour across four (plus one) mathematical puzzles that I encountered during my career. Here is a paper based on these lectures which is meant for a very wide audience (in English)

Puzzles on trees, high dimensions, elections, computation and noise.

A  videotaped lecture is here. An earlier Hebrew version is

חידות על עצים , ממדים גבוהים, בחירות, חישוב ורעש

(It deals only with the first four puzzles.) A short videotaped Hebrew lecture (where I only discuss the first two puzzles and touch on the third) is here.

A drawing by my daughter Neta for puzzle number 3. (Based on a famous Florida recount picture.)

Summary: I will talk about some mathematical puzzles that have preoccupied me over the years, and I will also reveal to you some of the secrets of our trade. Continue reading

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

Friendship and Sesame, Maryam and Marina, Israel and Iran

Happy new (Jewish) year everybody.

Amazing scientific partnership  between Jordan, Cyprus, Egypt, Iran, Israel, Pakistan, the Palestinian Authority, and Turkey

SESAME (Synchrotron-light for Experimental Science and Applications in the Middle East) is a “third-generation” synchrotron light source that was officially opened in Allan (Jordan) on 16 May 2017. It is the Middle East’s first major international research center. It is very nice to see scientific cooperation between countries which otherwise do have some difficulties in their relationships.

Narrowing on Israel and Iran, there are many personal scientific friendships and collaborations between Israeli and Iranian scientists and it will certainly be nice to see in the future visits of Israeli scientists to Iran and of  Iranian scientists to Israel.

Marina, Maryam and Maths Friendships

Last July, Marina Ratner and Maryam Mirzakhani, two eminent mathematicians working in the area of dynamics passed away. Maryam was the first woman to win the Fields Medal, and Marina was, for a short time, a faculty member at my department and a close friend of the Hebrew University ever since.   Many of my colleagues knew both Marina and Maryam very well, and were great admirers of their personalities as much as their mathematics. Amie Wilkinson wrote a beautiful NYT article about Marina and Maryam’s mathematics: With Snowflakes and Unicorns, Marina Ratner and Maryam Mirzakhani Explored a Universe in Motion. (See also this HUJI memorial page, this post on Terry Tao’s blog, and this post on GLL.)

Amir Asghari had a nice idea to open a site dedicated to maths friendships in memory of Maryam Mirzakhani.  Let me also mention that there is a well known Israeli Facebook group for “digging into mathematics” that dedicated its profile picture to Maryam.



Posted in Obituary, Updates, Women in science | Tagged , , , , | 1 Comment

Elchanan Mossel’s Amazing Dice Paradox (your answers to TYI 30)

TYI 30 asked Elchanan Mossel’s Amazing Dice Paradox (that I heard from Yuval Peres yesterday)

You throw a die until you get 6. What is the expected number of throws (including the throw giving 6) conditioned on the event that all throws gave even numbers?

Most people answered 3.

Is it the right answer?


Continue reading

Posted in Combinatorics, Probability, Test your intuition | Tagged , | 63 Comments

TYI 30: Expected number of Dice throws

Test your intuition:

You throw a dice until you get 6. What is the expected number of throws (including the throw giving 6) conditioned on the event that all throws gave even numbers.

follow-up post

Posted in Combinatorics, Probability, Test your intuition | Tagged | 37 Comments

Test your intuition 29: Diameter of various random trees

Both trees in general and random trees in particular are wonderful objects. And there is nothing more appropriate to celebrate Russ Lyons great birthday conference “Elegance in Probability” (taking place now in Tel Aviv) than to test your intuition, dear reader, with questions about probability and trees.


Model 1: consider a set of n vertices {1,2,…,n} and a random spanning tree T on these vertices.

Test your intuition: What is the behavior of the diameter of T?

The diameter of a graph G is the maximum distance between pairs of vertices of G. The distance between a pair of vertices is the length of the smallest path between them. (For a tree there is a unique path.)

The answer and two follow up questions are below the fold.

Continue reading

Posted in Combinatorics, Probability, Test your intuition | Tagged , | 19 Comments

Micha Perles’ Geometric Proof of the Erdos-Sos Conjecture for Caterpillars

A geometric graph is a set of points in the plane (vertices) and a set of line segments between certain pairs of points (edges). A geometric graph is simple if the intersection of  two edges is empty or a vertex of both. A geometric graph is convex if the vertices are in convex position. A geometric caterpillar is a geometric tree that looks like this.

Theorem (Micha Asher Perles, mid 80s): Let T be a caterpillar with k edges. Every convex geometric graph with [n(k-1)/2]+1 edges  contains a simple copy of T. As a matter of fact, T can be embedded in G is an orientation preserving manner.

Proof: Let G be a convex geometric graph with n vertices and e edges. For every edge of G we will consider two half edges, where a half edge is a  small subinterval of the edge containing one of its vertices.  Thus G has 2e half edges.

Let T be a caterpillar with k edges.  Suppose that the left most non-leave, b,  of T has m+1 neighbors and let S be the geometric caterpillar obtained by removing from S the m left most neighbors of  a and the edges containing them. S has k-m edges. Let w denote the left most half edge of T.


An half edge u of G is good (for T) if we can embed T in an orientation preserving manner so that  w is mapped to u. Otherwise, u is bad.

the following is stronger than the Theorem.

Claim: There are at most (k-1)n bad half edges.

Proof by induction on T. For every vertex of G call its m left most half edges nasty. By induction G has at most (k-m)n bad (for S) half edges. Altogether there are at most (k-1m)n+mn=(k-1)m half edges which are either bad for S or nasty. We map every half edge y coming from a vertex x which is neither nasty nor bad for S to another half edge z as follows. First consider the half edge which is the (m+1)th to its left from x. (There is such a half edge because y was not nasty.)  The other half edge on the same edge. This half edge is good for T and therefore there are at most (k-1)n bad half edges for T. Sababa!

Remarks: See this post for a proof about geometric graphs by lice. The Erdos-Sos conjecture (whose solution for n> n_0(k) was achieved by Ajtai, Komlos and Szemeredi) asserts that a graph with n vertices and more than [(k-1)n/2] edges contains every tree with k edges. (See, here and here). The case where T is a path was proved by Erdos and Gallai.

Posted in Combinatorics, Geometry | Tagged , | 1 Comment

Touching Simplices and Polytopes: Perles’ argument

Joseph Zaks (1984), picture taken by Ludwig Danzer (OberWolfach photo collection)


The story I am going to tell here was told in several places, but it might be new to some readers and I will mention my own angle, recall and raise some questions  and provide some comments. You can read about it here: Martin Aigner and Günter Ziegler, Proofs from the Book Chapter 13 (freely available on Springer links), and also in Bela Bollobas, The Art of Mathematics – Coffee Time in Memphis.

Can you find  non-overlapping d-dimensional polytopes P_1,P_2,\dots ,P_k be, in \mathbb R^d, such that each pair of polytopes have (d-1)-dimensional intersection, and such that  P_i has f_i facets? In two dimensions k \le 4 (because K_5 is not planar) but in higher dimensions things are not clear. We call two d-polytopes in \mathbb R^d “touching” if they have (d-1)-dimensional intersection (no more, no less).

A special case of this problem deals with the case that all the P_is are simplices (thus having d+1 facets each) and then the question is how large k can be? The problem goes back to a 1956 paper by Bagemihl. A famous conjecture  by Bagemihl (space) and Baston (all dimensions) asserts that k \le 2^d. Joseph Zaks gave a beautiful example of 2^d simplices in \mathbb R^d with this property. Baston proved that in space k \le 9 and, based on his work and a great deal of extra effort, Joseph Zaks verified Bagemihl’s original conjecture! He thus proved that in space k \le 8. The conjecture in higher dimensions is wide open.

Let me show you a very simple proof by Micha A. Perles that k \le 2^{d+1}.

Let n be the overall number of hyperplanes supporting the facets of the polytopes and let H_1,H_2, \dots , H_n be these supporting hyperplanes. For each hyperplane H_i we denote the two closed half spaces determined by it by H_i^+ and H_i^-. Now let us suppose that in our family of polytopes there are r_j polytopes with j facets, j=d+1,d+2,\dots.



(*) \sum r_j 2^{-j} \le 1.

In particular, if all polytopes are simplices we get that k\le 2^{d+1}.

Proof (Micha A. Perles):  Consider a matrix M=(m_{ij}) whose rows correspond to the k polytopes and whose columns correspond to the n hyperplanes.

The entries are:

m_{ij}=1 if H_j contains a facet of polytope P_i, and P_i \subset H_i^+.

m_{ij}=-1 if H_j contains a facet of polytope P_i, and P_i \subset H_i^-.

Otherwise, m_{ij}=0.

Now replace each row of the matrix by new 2^{n-f_i} rows by replacing every zero entry by a \pm 1 entry in all possible ways.  (Recall that polytope P_i had f_i facets.)

Claim: All the new rows are distinct.

Proof: This is clear for two new rows coming from the same original row. Given two rows which correspond to distinct polytopes P_e and P_f, since these polytopes are touching, in the original rows there is a column j for which m_{ej}=1 and m_{fj}=-1 or the other way around. These pair of distinct entries remain unchanged when zeroes are replaced by \pm 1. Ahla!

Returning to the theorem, since there are altogether 2^n vectors of \pm 1 entries we get that

\sum _{i=1}^k 2^{n-f_i} = \sum_{j \ge d+1} r_j 2^{n-j} \le 2^n. Dividing by 2^n gives us the theorem.  Sababa!


Of course, we can ask if a stronger inequality is valid and propose that

Conjecture  (**): \sum r_j 2^{-j} \le 1/2.

Another question is when (for d \ge 3) can we realize “r-vectors” obeying the strong inequality (**) by a family of touching polytopes.

Twelve quick remarks:

  1. Perles’ argument is close in spirit to a proof technique in extremal combinatorics that we saw, for example, in the proof of Sperner’s theorem on antichains and in the proof of the “two family theorems“. (Here and below you can find links to earlier blog posts, but not to the precise location in those posts.)
  2. Inequality (*) resembles the LYM inequality.
  3. Zaks’ example of 2^d touching simplices in \mathbb R^d is beautiful. See his paper Neighborly family of 2^d simplices in E^d. (Or here.)
  4. Let us call a facet of a polytope in the family “free” if it does not touch any other polytope. Zaks made the following conjecture: In every family of touching d-simplices (d-polytopes) in \mathbb R^d, there is a free facet (to at least one of the polytopes.)
  5. In a family of touching simplices if every simplex has a free face then k\le 2^d. (More generally, for touching polytopes with this property (**) holds.)
  6.  It would be very nice to prove the 2^d upper bounds for families of touching simplices (and inequality (**) for families of touching polytopes) such that in the family and in every subfamily at least one simplex has a free facet.
  7. Related to comments 1 and 6. Is there an algebraic/topological proof of the known inequality which will enable to use Zaks’ free-facet conjecture? Possible role model: Lovasz’ algebraic proof (and geometric extension) of the two-family theorem.
  8. Two d-polytopes P,Q in \mathbb R^d are weakly touching if there is a hyperplane containing a facet of both that (weakly) separates them.
  9. Perles’ proof and inequality (*) extend for families of weakly touching polytopes. It may be the case that the conjectures of Bagemihl and Baston and inequality (**) extends for weakly touching polytopes.
  10. Zaks’ free-facet conjecture does not extend for weakly touching simplices.
  11. In my first meeting with Gunter Ziegler in 1984 we talked about this problem. (We had both worked on it previously).
  12. We use here again the convention of ending proofs with the words Walla and Sababa. The endings Ahla, Ashkara (for trivial proofs), and Fadiha (for wrong proofs) can also be used.

A   fantasy for attacking the problem based on points 4,6,7 above is given in the following figure

Coxeter’s MathSciNet review of Baston’s Book

Baston, V. J. D. , Some properties of polyhedra in Euclidean space.
International Series of Monographs in Pure and Applied Mathematics, Vol. 71 Pergamon Press, Oxford-Edinburgh-New York 1965 xi+209 pp.

F. Bagemihl [Amer. Math. Monthly 63 (1956), 328–329; MR0077132] considered a set of n tetrahedra (in three-dimensional space) which fit together without overlapping so that every two of them have a common boundary (part of a face) of positive area. After proving that n can be 8, and that n≤17, he conjectured that 8 is the greatest possible value of n. The author, in the first chapter, reaches the same conclusions independently, representing the arrangement by a matrix of n rows whose entries are all 1, 0 or -1. In the remaining nine chapters he reduces the upper bound from 17 to 9, still leaving for future research the possibility of an arrangement with n=9.

The presentation is enlivened by colorful nomenclature; for instance, one reads, on page 181, “As S3 contains five dotres and no treuns there are ten tripts in the matrix. As there are four naiks…” Although such passages are less poetic then “All mimsy were the borogoves, and the mome raths outgrabe”, there is again the comforting thought that each unfamiliar word is precisely defined in another part of the book. Moreover, the index reassures us that there are only 24 such words, including Lewis Carroll’s old friend, the dodo.

Reviewed by H. S. M. Coxeter


Posted in Combinatorics, Convex polytopes, Geometry, Open problems | Tagged , | Leave a comment

Where were we?

I was slow blogging, and catching up won’t be so easy. Of course, this brings me back to the question of what I should blog about. Ideally, I should tell you about mathematical things I heard about. The problem is that it is hard to do so in real-time. I can also try to write about older things and indeed one of my next posts will be about a beautiful geometric proof of Micha Perles for a special case of the Erdos-Sos conjecture about trees. I can also tell you a little about where we were. (In reverse chronological order.)

IMPA, Rio  and Peru

Just came back from a splendid visit to Peru and Brazil with my son Hagai. In Brazil I took part in the 31st Brazilian Mathematical Colloquium which was a wonderful event with many young people and a great deal of enthusiasm for mathematics.

Five-Puzzles lectures and papers

My talk at Rio was a general-audience personal tour across five mathematical puzzles that I encountered during my career. (Note to self: to write here about these puzzles.) In a second lecture I elaborated a bit more on the first puzzle and its connections to convexity. Apologies for my English. At least it seems that I am thinking before finally deciding to go with the wrong option, like “Did I succeed….ed” or “How come…s”

Elisha Netanyahu memorial lecture

Earlier, I gave a similar talk at the Technion – the Elisha Netanyahu Memorial Lecture. It was fascinating to learn about Elisha Netanyahu whom I did not know personally. Before the talk a nice written greeting by Benjamin Netanyahu (Elisha’s nephew) was read.


Discrete Geometry and Convexity

Imre Barany’s 70th birthday conference in Budapest was a very special event. And here is the playlist of the lectures and my lecture.

IMU meeting in Acre

I try not to miss the annual Israeli Mathematical Union meeting. This year it was in Acre with some excellent plenary addresses and a really great session in discrete mathematics and theoretical CS that Nathan Keller and I organized. I plan to tell you about some of the results from our session later.

 More pictures and links



From the top: Happy days, a lecture by Einat Wigderson and me at AviFest (clique for the video). Implementing interior point methods, implementing the simplex algorithm (click for a video), two pictures from Machu Pichu; my quantum puzzle paper translated into Chinese, balancing a twister (click for a video),  at IPAM with Yoshiharu Kohayakawa (Yoshi) and Rob Morris, and with Gugu (Carlos Gustavo Moreira); Hugo mentions KKL and BKKKL! (all talks of the probability school and Brazilian Colloquium are available on IMPA You Tube channel), with Ron Holzman and Nathan Netanyahu.

The decline of confidence and ability with age.

When commenting on polymath projects and in other mathematical occasions I sometimes make silly remarks and even then I usually regard it as a positive contribution to the discussion.  When I made this remark on poymath12, which turned out to be quite silly a few minutes later, I somehow lost my confidence a little and had a feeling of “losing it”. I was a little sorry about the matter but then my next thought about it was:

This is wonderful, because it will give us an opportunity to examine the decline of confidence and ability with age.

Well, the decline of confidence and ability with age, is overall sad, but arguably monitoring and understanding this phenomenon is important. I was later happier about other polymath12 comments and proposed directions, but the aging angle is something to keep in mind. (Disclaimers: This section is for entertaining purposes only; It follows a long tradition in combinatorics, Paul Erdos started complaining about old age when he was 28.)

Great honors

Last but not the least, I am proud and happy to report on several important honors given to me. I was elected to the Israeli Academy of Science and Humanities, and also to the Academia of Europe, and as an honorary foreign member to the Hungarian Academy of Science. I was also chosen to give a plenary address at the 2018 ICM in Rio which is also a great honor and a great challenge.   I am very happy and thankful for these unexpected honors.

A short Hebrew general-audience talk about (two and a half) puzzles at the Israeli Academy of Science and Humanities.

Alex Lubotzky and me are both invited plenary ICM 2018 speakers in Rio. In 2004 we explored  Rio and Brazil together with our wives and in 1994 we were both invited speakers at the ICM in Zurich. Here we collaborate on a Clay foundation video describing (a little of) the mathematics of Larry Guth and Nets Katz. (Click on the picture for the video.)

Update: Let me make a quick update with additional links going chronologically even a few months backward. In 2016 I gave several lectures on quantum computers (explaining my research and analysis on why they are not possible). I gave a series of three lectures in Bloomington, Indiana in a very enjoyable trip (my second) to the department. Here are the slides of lectures (Lecture I: The quantum computer puzzle, Lecture II: Elections!, Lecture III: What can we learn from the failure of quantum computers.). At that same year I also gave the Pekeris lecture at the Weizman Institute again on quantum computers (Here are the slides, the first few slides are about Pekeris and connections of his work to quantum computers and to dating the earth). In 2016, I participated in a truly amazing conference celebrating the work of Jean Bourgain, and gave a lecture (here is the video) on questions I asked Jean along the years.  (No quantum staff, I afraid.) Here is the full playlist. Here is, again the link to my plenary lecture at the 2016 European Congress of Mathematics (7ECM),  and, I also found on-line my lecture from Noga fest (full playlist).

Also, here are the first slides for my Technion  devoted to Elisha Netanyahu and his contemporaries and his Ph.D from our library.


Posted in Combinatorics, Conferences, Movies, Updates | Tagged , | 2 Comments

Call for nominations for the Ostrowski Prize 2017


Call for nominations for the Ostrowski Prize 2017

The aim of the Ostrowski Foundation is to promote the mathematical sciences. Every second year it provides a prize for recent outstanding achievements in pure mathematics and in the foundations of numerical mathematics.

The prize has been awarded every two years since 1989. The most recent winners are Ben Green and Terence Tao in 2005; Oded Schramm in 2007; Sorin Popa in 2009; Ib Madsen, David Preiss, and Kannan Soundararajan in 2011; Yitang Zhang in 2013; and Peter Scholze in 2015.

The jury invites nominations for candidates for the 2017 Ostrowski Prize.  Nominations should include a CV of the candidate, a letter of nomination, and 2-3 letters of reference. Nominations should be sent to the Chair of the jury for 2017, Gil Kalai (Hebrew University of Jerusalem, Israel), by June 30, 2017.

(Because of some technical difficulties in advertising the deadline was extended from the original deadline of May 15, 2017.)

Links: Ostrowski Prize (Webpage) Ostrowski Prize (Wikipedea)

Please share this information.

Posted in Updates | 1 Comment

Problems for Imre Bárány’s Birthday!


On June 18-23 2017 we will celebrate in Budapest the 70th birthday of Imre Bárány. Here is the webpage of the conference. For the occasion I wrote a short paper with problems in discrete geometry, mainly around Helly’s and Tverberg’s theorem. This represents
one of the areas on which Imre Bárány had immense impact. Here is the paper: Problems for Imre Bárány’s birthday.

Happy birthday, dear Imre

(Our 1999 picture was taken by Emo Welzl.)

Posted in Combinatorics, Conferences, Open problems | Tagged , | Leave a comment