A Diameter Problem (2)

2. The connection with Hirsch’s Conjecture

The Hirsch Conjecture asserts that the diameter of the graph G(P) of a d-polytope P with n facets is at most n-d. Not even a polynomial upper bound for the diameter in terms of d and n is known. Finding good upper bounds for the diameter of graphs of d-polytopes is one of the central open problems in the study of convex polytopes. If d is fixed then a linear bound in n is known, and the best bound in terms of d and n is n^{\log d+1}. We will come back to these results later.

One basic fact to remember is that for every d-polytope P, G(P) is a connected graph. As a matter of fact, a theorem of Balinski asserts that G(P)$ is d-connected.

The combinatorial diameter problem I mentioned in an earlier post (and which is repeated below) is closely related. Let me now explain the connection. 

Let P be a simple d-polytope. Suppose that P is determined by n inequalities, and that each inequality describes a facet of P. Now we can define a family \cal F of subsets of {1,2,…,n} as follows. Let E_1,E_2,\dots,E_n be the n inequalities defining the polytope P, and let F_1,F_2,\dots, F_n be the n corresponding facets. Every vertex v of P belongs to precisely d facets (this is equivalent to P being a simple polytope). Let S_v be the indices of the facets containing v, or, equivalently, the indices of the inequalities which are satisfied as equalities at v. Now, let \cal F be the family of all sets S_v for all vertices of the polytope P.

The following observations are easy.  

(1) Two vertices v and w of P are adjacent in the graph of P if and only if |S_v \cap S_w|=d-1. Therefore, G(P)=G({\cal F}).

(2)  If A is a set of indices. The vertices v of P such that A \subset S_v are precisely the set of vertices of a lower dimensional face of P. This face is described by all the vertices of P which satisfies all the inequalities indexed by i \in A, or equivalently all vertices in P which belong to the intersection of the facets F_i for i \in A.

Therefore, for every A \subset N if {\cal F}[A] is not empty the graph G({\cal F}[A]) is connected – this graph is just the graph of some lower dimensional polytope. This was the main assumption in our abstract problem.

Remark: It is known that the assertion of the Hirsch Conjecture fails for the abstract setting. There are examples of families where the diameter is as large as n-(4/5)d.

1. A Diameter problem for families of sets

Let me draw your attention to the following problem:

Consider a family \cal F of subsets of size d of the set N={1,2,…,n}.

Continue reading

Two Very Early Problems, a Simple Solution, and a New Problem



As an undergraduate student whenever I studied some subject I tried to come up with problems. Many of these problems were artificial or silly and, of course, I forgot most of them. But a few still make sense. Here are two problems: 

1) Let B be the unit ball (or the unit cube) in R^d. Does every function from B to B which is the differential of a real function on B have a fixed point?

2) Is there a common generalization for Sylows’s theorem and Frobenius’s theorem?

Updates:A few typos corrected; thanks Lior! A remark by David Speyer suggests that both results we would like to find a common generalization to, are due to Frobenius. (Who was motivated by Sylow’s theorems.) Emmanuel Kowalski’s was partially motivated by these problems to present an old sporadic problem of his. (It is a mystery for me why his post is not mentioned as a track-back in this post.) 

1) A fixed point theorem for differentials?

One of the delightful theorems you learn in the first year of undergraduate studies (and later teach as a TA, and later teach as a professor) is the intermediate value theorem. Continue reading

Surprising Math

1. A pleasant surprise

When I worked on the diameter problem for d-polytopes with n facets. I was aiming to prove an upper  bound of the form n^{\log d} but my proof only gave d^{\log n},

It was a pleasant surprise to note that n^{\log d}=d^{\log n}.

2. A bigger surprise

A few weeks ago James Lee gave a talk and proved a bound of the form (\log n)^{\log \log \log n}.   I was surprised to learn from him that (\log n)^{\log \log \log n} = ( \log \log n)^{\log \log n} .

(Update: I got it wrong at first, thanks guys)

This is an even more surprising special case of the formula above.

3.  Is it better to have the discount first?

Question: What is a better deal: A store that gives 12% student-discount after it adds a 12% value added tax to the price of the product? Or a store that first adds 12% tax on the entire sum and only then deducts 12% student discount?

Ohh, The way I asked this question the two alternatives are precisely the same. Let me ask it again: What is a better deal: A store that gives 12% student discount after adding a 12% value added tax to the price of the product? Or a store that first deducts the 12% student discount, and only then adds 12% tax on the new price? 

Continue reading

Plans and Updates

Jerusalem and Budapest




Monday, last week was the last day of lectures for the spring term here at the Hebrew U.  One outcome of the long professors’ strike was a very fruitful year for research seminars. We ran them during the strike and we run when we taught. I heard about quite a lot of nice developments recently. Zeev Dvir gave a talk on the finite field Kakeya problem. The proof was extremely simple to start with (see Tao’s post ) and Zeev’s presentation was even simpler. It is a very interesting question how, given Dvir’s proof, we should now view the connection between the finite field version of the problem and the original problem. Does Dvir’s proof support the possibility that the original problem is not as hard as feared? Does it support the view that the finite case is not related to the continuous case? (Both Tao and Laba discuss these questions.)

I will tell you in very rough terms (which represent my partial understanding of the matter) one recent wonderful development I heard about.  Kolmogorov and Sinai proved that the Entropy is an invariant for Bernoulli shifts under isomorphism.  Ornstein celebrated isomorphism theorem  asserts that entropy is the only invariant. Orenstein and Weiss studied other group actions, and extended these theorems to amenable groups. There were strong indications that free-group actions behave very differently. (There were examples where the entropy function went the wrong way for “factors”.) However, Lewis Bowen has just shown that for free-group action entropy is an invariant! (OK, I oversimplified matters here for the sake of telling the story.) And he further proved a similar result for all “sofic groups”, a strange notion of groups which is a mixture of amenable and residually finite groups that, as far as we know, may include all groups. Benji Weiss told us about it in the “basic notions seminar”, and a few weeks later another lecture was given by the man himself – Lewis Bowen – who came from Hawaii for a short visit.

And last week I participated in a meeting “Building Bridges” in Budapest honoring Laci Lovász for his birthday. A lot of interesting talks on extremal combinatorics, graph theory, optimization, probabilistic combinatorics, and theoretical computer science. I will come back to this meeting later but let me mention one talk which I found very surprising: Peter Winkler talked about his work with Rick Kenyon on branched polymers. Kenyon and Winkler found startling simple combinatorial proofs to starling results of Brydges and Imbrie, and proved further results. I hope to add a link to the actual presentation. Hungary is the discrete mathematics superpower and on top of that as Einat Wigderson recently made clear “The Hungarians are also much funnier”.  It was nice to meet many old friends (and annoy them, at times, with silly jokes). Here is Micky Simonovits and here you can see Endre Szemeredi, Anna Szemeredi, Szemeredi’s jacket and Szemeredi’s tie. I followed the name of the conference and talked about mathematics of social choice.




We had a few slow weeks on the blog and as the saying goes: “If you cannot do, plan, and if you cannot plan, plan plans.” Together with a little summary of previous posts, I will describe some of the things I plan to write next on this blog.

I plan five posts in the series about Extremal combinatorics. Part I was an introduction to the subject and dealt with extremal set theory. Part II was about simple extremal problems in plane geometry and additive number theory, and about difficult theorems which became quite easy in time. Extremal Combinatorics III will present several basic results in extremal set theory; Part IV will be about POSETS, and part V will present the Frankl-Wilson theorem, or, at least, special cases.

I gave four posts (I, II, III, IV) based on my lecture in Marburg, dealing with high dimensional Cayley formula. Richard Stanley gave a detailed remark on why the fantasy about weighted correct version of MacMahon’s conjecture for solid partitions is not what standard proofs of the plane partition case extend to. I plan a little series of posts on “f-vectors and homology,” which was the title of a paper with Bjorner in 1988 as well as of my talk in Stockholm.  However, before that I want to describe the “g-conjecture for spheres” a central problem in algebraic combinaorics.

We had several posts on convex polytopes.  I next plan to discuss the diameter problem for polytopal graphs (the Hirsch conjecture) and related questions on the simplex algorithm. (In fact, we already started.) The one proof I presented most often in lectures is my proof of the Blind-Mani theorem that asserts that simple polytopes are determined by their graphs. I will try to blog this proof, tell you some open problems around it, and write about a startling theorem of Eric Friedman who found a polynomial-time algorithm. I also updated the post on five open problems regarding convex polytopes and added two additional problems.

We talked about influence but not about a major technique which emerged in their study: Fourier Analysis of Boolean functions.” So we will discuss Boolean functions and their spectrum, and revisit influences and look at noise-sensitivity. Muli Safra will give a post on the Goldreich Levin theorem and related stuff.

So far our open discussion “Is mathematics a science” attracted a single (nice) comment, and the poem translation contest is still waiting for quality translations. Perhaps we can try an open discussion of a single theorem/problem and see how it goes. Meanwhile, have a look at the very successful discussion on Secret Blogging Seminar about the shy and secretive mathematicians, and how they triumph again and again.

Let’s talk some more on economics and rationality. And about sociel welfare functions and voting methods. We discussed some controversies related to rationality in this post, and the Notices book-review about economics and common sense supplied a source for two posts (1,2).  I was just told that along with Landsburg’s book itself, my book review might be translated to Arabic. Sababa!

I will tell you about my ideas regarding detrimental noise for quantum computations, but only after trying to describe something about the beautiful, deep, and surprising subject of quantum computation and quantum information. I will not do it before having at least one post about classical computation complexity. Meanwhile, let me link you to the classical post by Aaronson “Reasons to believe” (on why we believe that NP is not P). And while at it, look at “Reason to believe II” (on why many of us believe that quantum computers are feasible.) Read also Bernard Chazelle’s thoughts about alorithms and science.

The most successful link we had so far was  Continue reading

Our Department’s Quilt

Academic administation is a topic of great interest that desrves a special post. The highest post I served was as the department chair, and one thing I did was to acquire for the department a quilt by the artist Anna Maria Brenti. Of course, you are welcome to come and see it (and there are a few other things to see in the city of Jerusalem.) Meanwhile here are pictures: (Click for larger pictures.)



The artist Annamaria Brenti has a degree in Mathematics from the University of Florence; her interests gradually shifted to quilting while living in the U.S. Her quilts won international awards in major quilt shows in Europe and the United States. She has been an invited artist at several quilting events around the world, including the IX International Quilt Week in Yokohama (Japan) in 2001, the IX European Patchwork Meeting in Alsace (France) in 2003, the Pacific International Quilt Festival in Santa Clara (California, U.S.A.) in 2003, and the World of Quilting in Stoneleigh (U.K.) in 2003. She currently lives in Frascati (Rome, Italy).


You can read more  about the various mathematical objects on the quilt in the website of the Institute of Mathematics at the Hebrew University of Jerusalem.