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

Advertisements
Posted in Combinatorics, Probability, Test your intuition | Tagged | 36 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.

Theorem:

 

(*) \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), kalai@math.huji.ac.il 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

Twelves short videos about members of the Department of Mathematics and Statistics at the University of Victoria

Very nice mathematical videos!

Posted in Academics, Movies, What is Mathematics | Leave a comment

Jozsef Solymosi is Giving the 2017 Erdős Lectures in Discrete Mathematics and Theoretical Computer Science

                         

 

May 4 2:30-3:30; May 7 11:00-13:00; May 10 10:30-12:00

See the event webpage for titles and abstracts (or click on the picture below).

 

Posted in Combinatorics, Geometry, Updates | Tagged , | Leave a comment

Updates (belated) Between New Haven, Jerusalem, and Tel-Aviv

This is a (very much) belated update post from the beginning of March (2016).

New Haven

I spent six weeks in February (2016) in New Haven. It was very nice to get back to Yale after more than two years. Here is a picture from the spectacular Yale’s art museum.

piccaso

Micha Sageev’s construction. I got the gist of it (at last…)

A few years ago I wrote about amazing developments in low dimensional topology. Ian Agol proved the Thurston’s virtual Haken conjecture. The proof relies on earlier major works by Dani Wise and others (see this post) and an important ingredient was Micha Sageev work on cubical complexes arising from 3-manifolds. I remember thinking that as a mathematician in another field it is unrealistic for me to want to understand  these developments in any detail (which is not an obstacle for writing about them), but that one day I want to understand Sageev’s construction. At Yale, Ian Agol gave three lectures on his proof, mentioned a combinatorial form of Sageev construction, and gave me some references. A few days after landing Dani Wise talked at our seminar and he explained to me at lunch how it goes in details. (BTW, a few days before landing Micha Sageev gave a colloquium at HUJI that I missed.) I have some notes,  and it is not so difficult so stay tuned for some details in a future post!. (Update: I will need some refreshing for writing about it. But I can assure you that Micha Sageev’s construction is a beautiful combinatorial  construction that we can understand and perhaps use.)

Unorthodox PNT (and even weak forms of RH).

Hee Oh talked at Yale about various analogs of the prime number theorem (PNT) and in some cases even of weak forms of the Riemann hypothesis for hyperbolic manifolds and for rational maps. This is based on a recent exciting paper by Oh and Dale Winter. Some results for hyperbolic manifolds were known before but moving to dynamics of rational maps is completely new and it follows  a “dictionary” between hyperbolic manifolds and rational maps offered by Dennis Sullivan. It was nice to see in Oh’s lecture unexpected connections between the mathematical objects studied by three Yale mathematicians, Mandelbrot, Margulis, and Minsky. Are these results related to the real Riemann Hypothesis? I don’t know.

Weil conjectures (even for curves): from the very concrete to the very abstract,

Going well over my head I want to tell you about somethings I learned from two lectures. It is about Weil’s conjectures for curves including the  “Riemann hypothesis for curves over finite fields.”   One lecture is by Peter Sarnak and the other by Ravi Vakil. Both lectures were given twice (perhaps a little differently)  in Jerusalem and at Yale few weeks apart. Peter Sarnak mentioned in a talk the very concrete proof by Stepanov to the Rieman hypothesis for curves over finite fields. The proof uses some sort of the polynomial method, and it is this concrete proof  that is useful for a recent work on Markoff triples by Bourgain, Gamburd and Sarnak. Ravi Vakhil mentioned a very very abstract form of the conjecture or, more precisely, of the “rationality” part of it proved in 1960 by Bernard Dwork (yes, Cynthia’s father!). It started from an extremely abstract version offered by  Kapranov in 2000 to which Larsen and Lunts found a counterexample. A certain weaker form of Kapranov’s conjecture that Ravi discussed might still be correct. (A related paper to Ravi’s talk is Discriminants in the Grothendieck ring  by Ravi Vakil and Melanie Matchett Wood.)  These very abstract forms of the conjectues are also extremely appealing and it is especially appealing to see the wide spectrum from the very concrete to the very abstract. It is also nice that both the polynomial method and the quest for rationality (of power series) are present also in combinatorics.

HD expanders, HD combinatorics, and more.

Alex Lubotzky and I gave a  6-weeks course on high dimensional expanders. This was the fourth time we gave a course on the subject and quite a lot have happened since we first taught a similar course some years ago so it was quite interesting to get back to the subject. I certainly plan to devote a few posts to HD-expanders and Ramanujan complexes at some point in the future.

Update: There will be a special semester on high-dimensional combinatorics and the Israeli Institute for Advanced Studies in Jerusalem in the academic year 2017/2018.

At the Simons Center in NYC Rafał Latała gave a beautiful lecture on the solution by Thomas Royen  of the Gaussian correlation conjecture. Here is a review paper by Rafał Latała and Dariusz Matlak.

Update: Here is an article about this proof in Quanta magazine; and a blog post on GLL.

Polymath talks

I also gave three lectures at Yale about polymath projects (at that time both Polymath10 and Polymath11 were active), and a special welcome lecture to fresh Ph. D. potential students  POLYMATH and more – Mathematics over the Internet (click for the presentation) about polymath projects and mainly Polymath5, MathOverflow, mathematical aspects of Angry Birds and why they should all choose Yale.

An advantage of being 60.

One of repeated rather unpleasant dreams I had over the years (less so in the last decade)  was that the  Israeli army discovered that I still owe some months of service, and I find myself confusingly and inconveniently back in uniform. A few weeks (+ one year) ago I had a new variant of that dream appropriately scaled to my current age:  MIT discovered that I still owe some months of my postdoctoral service. This was much more pleasant!

Posted in Art, Combinatorics, Computer Science and Optimization, Number theory, Updates | Leave a comment