Monthly Archives: May 2008


“The fixed price to JFK is 28 dollars” said the taxi driver; “toll and tips not included, and I want the two dollars and seventy five cents for the toll upfront.” I reached to my wallet, dug eleven quarters and handed them to him. He carefully checked the quarters and said: “If you’re wondering why I want the toll money here, it is all because of the Drachmas.” “The Drachmas?” I asked. “Yes” said the driver. “They want to take me to trial for putting drachmas instead of quarters in the toll machine.” Apparently, using 100 Greek Drachma coins, which are almost of no value, instead of US quarters became quite a problem. “No matter how much I tell them that I put whatever the clients give me in the machine they still do not believe me, and want to bring me to trial. Therefore I now check the quarters the clients give me here in New York, in the light.” “I see” I said. I felt sorry for him. He was getting into serious trouble because of greedy, heartless passengers. 

Continue reading

Five Open Problems Regarding Convex Polytopes


The problems 

1. The 3^d conjecture

A centrally symmetric d-polytope has at least 3^d non empty faces.

2. The cube-simplex conjecture

For every k there is f(k) so that every d-polytope with d \ge f(k) has a k-dimensional face which is either a simplex or combinatorially isomorphic to a k-dimsnional cube.

3. Barany’s question

For every d-dimensional polytope P and every k, 0 \le k \le d-1,  is it true that f_k(P) \ge \min (f_0(P),f_{d-1}(P))?

(In words: the number of k-dimensional faces of P is at least the minimum between the number of vertices of P and the number of facets of P. )

4.  Fat 4-polytopes

For 4-polytopes P, is the quantity (f_1(P)+f_2(P))/(f_0(P)+f_3(P)) bounded from above by some absolute constant? 

5.  five-simplicial five-simple polytopes

Are there 5-simplicial 5-simple 10-polytopes? Or at least 5-simplicial 5-simple d-polytope for some d?

(A polytope P is k-simplicial if all its faces of dimension at most k, are simplices. A polytope P is k-simple if its dual P* is k-simplicial.)

And on a personal note: My beloved, beautiful,  and troubled country celebrates 60 today: happy birthday! 

Update (May 12): David Eppstein raised in a followup a sort of a dual question to Barany’s. For a d-polytope with n vertices and n facets what is the maximal number of k-faces. For a fixed d and large n the free join of pentagons is conjectured to give asymptotically the best upper bound.

Update (July 29) Gunter Ziegler reminded me of the following additional problem of Barany: Is the number of saturated chains in a d-polytope bounded by some constant (depending on d) times the total number of faces (of all dimensions) of the polytope. A saturated flag is a 0-face inside a 1-face inside a 2-face … inside a (d-1)-face. 

Continue reading

A Meeting at Marburg

  Just returning from a cozy two days discrete-math workshop in Marburg. A very nice mixture of participants and topics. The title of my talk was “Helly theorem, hypertrees and strange enumeration” and I plan to blog about it sometime soon. A few hours before taking off, Aner Shalev told me that a 1951 conjecture by Ore asserting that every element in a non abelian finite simple group is a commutator have just been proved by a group of four researchers – Aner himself and Liebeck, O’Brien and Tiep.  (Ore himself proved that for A_n every element is a commutator.) The basis for a very complicated inductive proof required computer works and the final OK came four hours before Aner gave a lecture about it! 

The talks in Marburg were very interesting.

Day 1:Enumerative combinatorics techniques and results related to the asymptotic conjectured formula for the number of self avoiding random walks (a holy grail in statistical mechanics);  Continue reading

Extremal Combinatorics I: Extremal Problems on Set Systems

The “basic notion seminar” is an initiative of David Kazhdan who joined HU math department  around 2000. People give series of lectures about basic mathematics (or not so basic at times). Usually, speakers do not talk about their own research and not even always about their field. I gave two lecture series, one about “computational complexity theory” a couple of years ago, and one about extremal combinatorics or Erdös-type combinatorics a few months ago, which later I expanded to a series of five+one talks at Yale. One talk was on  the Borsuk Conjecture,  which I will discuss separately, and five were titled: “Extremal Combinatorics: A working tool in mathematics and computer science.”  Let me try blogging about it. The first talk was devoted to extremal problems concerning systems of sets.



 Paul Erdös

1. Three warm up problems

Here is how we move very quickly from very easy problems to very hard problems with a similar flavour.

Problem I: Let  N = {1,2, … , n } . What is the largest size of a family \cal F  of subsets of N such that every two sets in \cal F have non empty intersection? (Such a family is called intersecting.)

Continue reading