Monthly Archives: August 2009

Igor Pak’s “Lectures on Discrete and Polyhedral Geometry”


Here is a link to Igor Pak’s  book on Discrete and Polyhedral Geometry  (free download) . And here is just the table of contents.

It is a wonderful book, full of gems, contains original look on many important directions, things that cannot be found elsewhere, and great beyond great pictures (which really help to understand the mathematics). Grab it!



Test Your Intuition (9)

Click on the picture if you wish to read about the “Mars effect”  

A) You want to test the theory that people who were born close to noon on July 7 are unusually tall. You choose randomly 100 Norwegian men over 25 years old and discover that the one person born closest to noon of 7/7 is the 15th tallest among them. Then you chose 100 Nigerian women and discover that the woman born closest to noon on July 7 is the 10th tallest. You figure out that without the putative effect being real (in other words, under the null hypothesis)  the chance for such results occuring at random is 1/10 times 3/20 which is 1.5%, and conclude that this lends significant support to your theory. Are you correct?

B) In a certain scientific area, the level of significance required for a statistical test is 5%.  Would it serve the quality of scientific papers in this area to reduce the required significance level to, say, 0.5%, in order to exclude publishing papers which report experiments that were successful by sheer chance?

The Polynomial Hirsch Conjecture: Discussion Thread


This post is devoted to the polymath-proposal about the polynomial Hirsch conjecture. My intention is to start here a discussion thread on the problem and related problems. (Perhaps identifying further interesting related problems and research directions.)

Earlier posts are: The polynomial Hirsch conjecture, a proposal for Polymath 3 , The polynomial Hirsch conjecture, a proposal for Polymath 3 cont. , The polynomial Hirsch conjecture – how to improve the upper bounds .

First, for general background: Here is a  chapter that I wrote about graphs, skeleta and paths of polytopes. Some papers on polytopes on Gunter Ziegler’s homepage  describe very interesting and possibly relevant current research in this area,  and also a few of the papers under “discrete geometry” (which follow the papers on polytopes) are relevant. Here are again links for the recent very short paper by  Freidrich Eisenbrand, Nicolai Hahnle, and Thomas Rothvoss, the 3-pages paper by Sasha Razborov,  and to Eddie Kim and Francisco Santos’s survey article on the Hirsch Conjecture.

Here are the basic problems and some related problems. When we talk about polytopes we usually mean simple polytopes. (Although looking at general polytopes may be of interest.)

Problem 1: Improve the known upper bounds for the diameter of graphs of polytopes, perhaps finding a polynomial upper bound in term of the dimension d and number of facets n.

Strategy 1: Study the problem in the purely combinatorial settings proposed in the EHR paper.

Strategy 2: Explore other avenues.

Problem 2: Improve  the known lower bounds for the problem in the abstract setting.

Strategy 3: Use the argument for upper bounds as some sort of a role model for an example. 

Strategy 4:Try to use recursively mesh constructions as those used by EHR.

Problem 3: What is the diameter of a polytopal digraph for a polytope with n facets in dimension d.

A polytopal digraph is obtained by orienting edges according to some generic linear objective function. This problem can be studied also in the abstract setting of shellability. (And even in the context of unique sink orientations.)

Problem 4: Find a (possibly randomized) pivot rule for the simplex algorithm which requires, in the worse case, small number of pivot steps.

A “pivot rule” refers to a rule to walk on the polytopal digraph where each step can be performed efficiently.

Problem 5: Study the diameter of graphs (digraphs) of specific classes of polytopes. 

Problem 6: Study these problems in low dimensions.

Here are seven additional relevant problems.

Problem 7: What can be said about expansion properties of graphs of polytopes? Continue reading

Impossibility Result for “Survivor”

Consider a set of n agents and a directed graph where an edge (i,j) means that agent i supports or trusts agent j. We wish to choose a subset C of size k of trustworthy agents. Each agent’s first priority is to be included in C. We want to find a function from directed graphs of trust, to k-subsets C of the vertices. We require two axioms

Axiom 1: If exactly one player is trusted by some other player then this player will be selected to the set C of trustworthy players.

Axiom 2: A player cannot prevent not being selected to C by misreporting his truthful judgement of his fellow players (even if he knows the way other players are going to vote).

Axiom 2 is referred to as “strategy proofness“.

Impossibility theorem (Alon, Fischer, Procaccia and Tennenholtz): For any k, 1\le k\le n-1 there is no mechanism for choosing the k-subset C of trustworthy agents that satisfies Axioms 1, 2.  

A special case of the theorem, when k=n-1, can be described in terms of the TV reality game “survivor”. Continue reading

School Bus to Ramle


We had just come back to Israel from Palo Alto after spending a sabbatical year there and my child was starting school. I walked down with him to wait for the school bus. To my great surprise it was a yellow school bus just like in the US. The school bus driver checked the name and said “Yes, we are going to Ramle, get on”. “To Ramle?” I screamed “Why Ramle?”. Ramle is a small town 50 kilometers from Jerusalem. I walked up quickly and asked my wife “Ramle? why Ramle?” My wife listened carefully and replied: “Do you think it is a bad idea to send the child to Ramle?” “Of course!” I said. “It is too late now”, said my wife, “You shoule have thought about it while we were still in the US.” Continue reading