Five open problems regarding convex polytopes

May 7, 2008 by Gil Kalai

  

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! 

Read the rest of this entry »

A meeting at Marburg

May 5, 2008 by Gil Kalai

  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);  Read the rest of this entry »

Extremal combinatorics I: Extremal problems on set systems

May 1, 2008 by Gil Kalai

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.) 

Read the rest of this entry »

Combinatorics, mathematics, academics, polemics, …

April 29, 2008 by Gil Kalai

1. About:

My name is Gil Kalai and I am a mathematician working mainly in the field of Combinatorics.  Within combinatorics, I work mainly on geometric combinatorics and the study of convex polytopes and related objects, and on the analysis of Boolean functions and related matters. I am a professor at the Institute of Mathematics at the Hebrew University of Jerusalem and also have a  long-term visiting position at the departments of Computer Science and Mathematics at Yale University, New Haven.  

 

 Gosset polytope- a hand drawing by Peter McMullen of the plane projection of the 8-dimensional 4-simplicial 4-simple Gosset polytope. Read the rest of this entry »