Monthly Archives: January 2009

Mathematics, Science, and Blogs

Michael Nielsen wrote a lovely essay entitled “Doing science online” about  mathematics, science,  and blogs. Michael’s primary example is a post over Terry Tao’s blog about the Navier-Stokes equation and he suggests blogs as a way of scaling up scientific conversation. Michael is writing a book called “The Future of Science.” He is a strong advocate of doing science in the open, and regard these changes as truly revolutionary.  (The term “Science 2.0” is mentioned in the remarks.)

Michael’s post triggered Tim Gowers to present his thoughts about massive collaboration in mathematics, and this post is also very interesting with interesting follow-up remarks.  Tim Gowers mentioned the n-category cafe as a place where a whole research programme is advanced on a blog. Terry Tao mentioned comments on posts on his open-problems series as having some value. He  mentioned, in particular, the post on Mahler’s conjecture. (Also I think some discussions over Scott Aaronson’s blog had the nature of discussing specific technical math (coming from CS) problems.)

Tim actually proposes an experiment: trying to solve collectively a specific math problem. This would be interesting!!! I suppose we need to give such an effort over a blog a longer than ususal life-span – a few months perhaps. (And maybe not to start with a terribly difficult problem.) (What can be an appropriate control experiment though?)

Ben Webster in “Secret blogging seminar”  mentioned, in this context, earlier interesting related posts about “Working in secret“.  

Christian Elsholtz mentioned on Gowers’s blog an intermediate problem (called “Moser’s cube problem”) where you look not for combinatorial lines (where the undetermined coordinates should be 1 in x 2 in y and 3 in z), and not for an affine line (where it should be 1,2,3 in x y and z in any order), but for a line: it can be 1 in x 2 in y and 3 in z or 3 in x 2 in y and 1 in z. 

Update: Things are moving fast regarding Gowers’s massive collaboration experiment. He peoposes to study together a new approach to the k=3 “density Hales -Jewett theorem”. A background post apears here. Hillel Furstenberg and Izzy Katznelson’s proof of the density Hales-Jewett theorem was a crowning achievement of the ergodic theory method towards Szemeredi’s theorem. Like the case for Furstenberg’s proof of Szemeredi’s theorem itself the case k=3 was considerably simpler and had appeared in an earlier paper by Hillel and Izzy. The recent extensions of Szemeredi regularity lemma that led to simpler combinatorial proof of Szemeredi’s theorem did not led so far to simpler proofs for the density Hales-Jewett case. If you look at Tim’s background post let me ask you this: What is the case k=2 of the density Hales-Jewett’s theorem? It is something familiar that we talked about! 

Here is a particularly silly problem that I suggested at some point along the discussions: How large can a family of subsets of an n-element set be without having two sets A and B such that the number of elements in A but not in B is twice the number of elements in B but not in A?

Update: This problem was completely reolved by Imre Leader and Eoin Long, their paper Tilted Sperner families contains also related results and conjectures.

Massive collaboration in art (click the picture for details)

Q: What is the case k=2of the density Hales-Jewett’s theorem? A: It is  Sperner’s theorem! (that we discussed in this post.)

I will keep updating about news from Tim’s project. [Last update is from October 21].  More updates: Tim’s project is getting quickly off the ground. A useful wiki was established. More update: It is probably successful

Continue reading



I just saw in “Shtetl Optimized” that the Linial-Nisan conjecture regarding AC^0 circuits have been proved by Mark Braverman. Scott’s post describes the conjecture as well as related open problems in computational complexity. (Scott offers  $100 for a proof that Fourier Checking is not in AM, $200 for a proof that it’s not in PH.) After many years of no news the case of depth two circuits was proved by Louay Bazzi about a year ago and a simpler proof was found by Razborov. Here is a post on the depth two case from “In theory“. 

Bazzi             m2


L. Bazzi                     M. Braverman

 A bit more: There are further posts about this development in  Computational Complexity  (by Lance) and in In theory.

All three posts describe the results in some details, Luca discusses connection with random 3SAT problems and Scott mentions some natural connections with quantum computation. Scott also gives a link to his related FOCS tutorial on the “polynomial method”.

Here is the description of Braverman’s result taken from “computational complexity”.

“Braverman shows that no poly-logarithmically independent distribution can be distinguished from a truly random distribution by a polynomial-size constant-depth circuit.

A r-independent distribution over binary strings of length n means that for every set of r bits are uniformly distributed over the 2r possible values for those bits. We can create r-independent distributions using O(r log n) truly random bits.

Braverman shows that no depth-d size-m circuit of AND, OR and NOT gates can distinguish between a truly uniform distribution and any r-independent distribution with r = (log m)O(d2). ”


Here is a problem (perhaps silly) that comes to mind:  Is the conclusion of the Linial-Nisan conjecture (=Braverman’s result) holds for Monotone TC^0 circuits, namely to circuits with (monotone) threshold gates? (I may ask around.)   (As Luca pointed out, we can certainly cannot hope for the full statement of the theorem; I am not sure about a weak version.)


organic chaos

What is the correct picture of our world? Are noise and errors part of the essence of matters, and the beautiful perfect patterns we see around us, as well as the notions of information and computation, are just derived concepts in a noisy world? Or do noise and errors just express our imperfect perception of otherwise perfect laws of nature? Talking about an inherently noisy reality may well reflect a better understanding across various scales and areas.

IPAM Fall 2009


Combinatorics: Methods and Applications in Mathematics and Computer Science

September 8 – December 11, 2009


Scientific overview: Combinatorics is a fundamental mathematical discipline as well as an essential component of many mathematical areas. It studies discrete objects and their properties. Although it is probably as old as the human ability to count, the field experienced tremendous growth during the last fifty years. This program will focus specifically on several major research topics in modern Discrete Mathematics. These topics include Probabilistic Methods, Extremal Problems for Graphs and Set Systems, Ramsey Theory, Additive Number Theory, Combinatorial Geometry, Discrete Harmonic Analysis and its applications to Combinatorics and Computer Science. We aim to foster interaction between researchers in these rather diverse fields, to discuss recent progress and to communicate new results. We would like also to put an emphasis on the exchange of ideas, approaches and techniques between various areas of Discrete Mathematics and Computer Science and on the identification of new tools from other areas of mathematics which can be used to solve combinatorial problems.


I am taking part in the organization of this promising Combinatorics semester at IPAM. Benny Sudakov is the main force behind it. Here is the schedule of workshops. (Of course there will be activities during the whole semester.)

(Update:  linked fixed)

Telling a Simple Polytope From its Graph

Peter Mani  (a photograph by Emo Welzl)

Simple polytopes, puzzles


Micha A. Perles conjectured in the ’70s that the graph of a simple d-polytope determines the entire combinatorial structure of the polytope. This conjecture was proved in 1987 by Blind and Mani and shortly afterwards I gave a simple proof which I like very much to present. 

Let P and Q be two simple d-dimensional polytopes. Let \psi be a bijection from the vertices of P to the vertices of Q which maps edges to edges. In other words, \psi is an isomorphism between the graph G(P) of P to the graph G(Q) of Q. Does \psi extend uniquely to a combinatorial isomorphism between P and Q? The answer is ‘yes’ but the argument is not so easy. There are also several related open problems.

Eric Friedman


A quick reminder about simple polytopes. A d-polytope P is simple if every vertex v of P is contained in d edges. (Equivalently, if the dual polytope P^* is simplicial.) Thus the graph G(P) of a simple d-polytope P is a d-regular graph. The crucial property of simple polytopes that we use is that for every vertex v of P and every collection of k edges of P containing v there is a unique k-face of P which contains v and these k edges.   

Among the famous simple polytopes are the cubes and simplices (in any dimension), polygons in the plane, and the dodecahedron in dimension 3 (but not the icosahedron or octahedron).

More background on polytopes can be found at the end of the post. (It is taken from this post presenting five open problems regarding polytopes.).

Good orderings, unique sink acyclic orientations, and shelling.

Consider a total ordering < of the vertices of a simple d-polytope P .  A vertex v is a local maximum if for every neighbor w of v, w<v. Of course, the maximum vertex in P with respect to the ordering is a local maximum.   An ordering of the vertices of P is called good, if for every face F  of P every local maximum in F is the global maximum in F.

( Just to make it clear: a vertex v in F is a local maximum in F, if for every neighbor w of v in F, w<v. The global maximum in F is the maximum vertex of F with respect to <.)

There are several variations of this notion. Instead of talking about the entire ordering we can talk just about the orientation it induces on edges of the graph. We orient an edge \{v,u\} from v to u if v < u. This is an acyclic orientation of the graph and being good or bad depends only on the orientation. Good orientations are called “unique-sink acyclic orientations”.  Also, as we will mention later, good orderings of the vertices of a simple polytope are closely connected to shelling order on the facets of the dual polytope.

The proof: part I

Let G be the graph of a simple d-polytope P.

The crucial claim

Given an ordering < of the vertices of the polytope  we define the degree of a vertex v, denoted by deg_<(v)  as the number of neighbors of v which are smaller than v with respect to the ordering. Let h_k^< be the number of vertices of degree k. Consider the following expression:

f^< = h_0^< +2 h_1^< + \dots + 2^kh_k^< + \cdots +2^nh_n^<

Continue reading