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!
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?
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 and number of facets .
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
Consider a set of agents and a directed graph where an edge means that agent supports or trusts agent . We wish to choose a subset of size of trustworthy agents. Each agent’s first priority is to be included in . We want to find a function from directed graphs of trust, to k-subsets 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 of trustworthy players.
Axiom 2: A player cannot prevent not being selected to 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 , there is no mechanism for choosing the -subset of trustworthy agents that satisfies Axioms 1, 2.
A special case of the theorem, when , can be described in terms of the TV reality game “survivor”. Continue reading
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
Here is an answer to “Test your intuition (8)”. (Essentially the answer posed by David Eppstein.)
(From Wolfram Mathworld)
Buffon’s needle problem asks to find the probability that a needle of length will land on a line, given a floor with equally spaced parallel lines at distance one apart. The problem was posed by Georges-Louis Leclerc, Comte de Buffon (1707 – 1788).
There is a familiar computation showing that when the probability is . A computation-free proof can be found in these pages on geometric probability written mostly by Molly McGinty. (They were pointed to me by Sergiu Hart.)
Briefly the computation-free argument goes as follows:
1) Consider the expected number of crossings of a needle with the lines rather than the probability of crossing.
2) Allow also polygonal needles.
3) Show, based on linearity of expectation, that for a polygonal needle the expected number of crossings is a linear function of the length of the needle.
4) Consider now a circular needle of radius 1/2. Note that with probability one it has two crossings with the lines. Deduce that .
This gives a proof for Buffon’s needle problem. But now consider any closed planar curve with constant width one. Again with probability one it will have two crossings with the parallel lines. Therefore, it has the same perimeter as the circle.
Update: The argument above Continue reading
Consider all planar sets A with constant width 1. Namely, in every direction, the distance between the two parallel lines that touch A from both sides is 1. We already know that there exists such sets other than the circle of radius 1/2.
Among all these sets which one has the largest perimeter? the smallest perimeter?