# Cosmonaut: Michal Linial

Ladies and gentelmen, I am very happy to present to you:

## A story by Michal Linial

I am back from the airport… not in the best mood for a long discussion but quite open to hear refreshing political statements. 50 minutes taxi ride that is all what it takes… This time, the communication took its own turns… I start with my regular question: “What is new this week”. This time, my Russian Taxi driver ignored my question and asked back: “How many planets are there?” I told him that to the best of my knowledge there are 9 planets that orbit around the sun. Really, he shouted: “my wife tells me there are 8 and she tells me she is a cosmonaut” and he continues, she knows nothing! I said that there might be some debate, so 8 is a good number and probably I got confused. My Taxi driver got really mad now: “You are not a cosmonaut and you know better”.
Two minutes later, he asks me again “how old is the earth”. This time I was a bit less decisive and told my taxi driver that I am not sure, but the accepted number is 4-5 billion years. To make sure this time there will be no conflicts with his marriage, I immediately added, the universe is much older, also, many people believe that the earth is much younger. My taxi driver now is very excited and answers me without hesitation: “You see, I can not even ask my wife this question, she says she is a cosmonaut, but I am sure that if I ask her, she will not know”… Continue reading

# The Golden Room and the Golden Mountain

Christine Björner’s words at the Stockholm Festive Combinatorics are now available to all our readers. What makes this moving and interesting, beyond the intimate context of the conference, is our (mathematician’s) struggle (and usually repeated failures) to explain to others what we are doing and why we are doing it.

## Christine Björner

I want to tell you a story about Anders. Actually two stories. The story of The Golden Room. And the story of The Golden Mountain.

I’ll begin with the Golden Room.

Once when I had seen Anders, night after night, week after week, working at his desk, totally immersed in a world of his own, I asked him this question: Can you explain to me what you are doing? And he answered: Christine, I have found the most beautiful room. The whole room is a mosaic of gold, dazzling in its splendour. What I am trying to do is make this room visible to others.

I am not a mathematician, but this metaphor gave me an insight into the magical world that all of you who have come to the Festive Combinatorics conference share. I want to honour today, in Anders, and all of you, not only your beautiful minds, but your intuition, your persistence, and your passion for truth.

A papyrus showing Queen Ankhes-Tut, wife of King Tut, with her husband in the golden room. The Egyptian Museum, Cairo.

Now I will tell you the second story. The story of The Golden Mountain.

# Amir Ban on Deep Junior

Ladies and Gentelmen: Amir Ban (right, in the picture above) the guest blogger, was an Israeli Olympiad math champion in the early 70s, with Shay Bushinsky he wrote Deep Junior, and he is also one of the inventors of the “disc on key”. This post is about computer chess.

Let me introduce myself: I’m Amir Ban, and I wrote the computer chess program Junior, also known as Deep Junior. When Gil invited me to guest-blog for him on the subject of computer chess, I was honored and pleased, but what can I write to introduce the subject to the uninitiated? Well, as luck has it, I participated last week in a unique event in Barcelona, Spain: a man with machine vs. machine match! The “man” was veteran grandmaster and Spanish champion Miguel Illescas. The “machine” he assisted himself by was my own Junior 10 (a commercially available product) on his Toshiba notebook. On the other side of the board was my latest Deep Junior 11, due to be released later this summer, running on an ordinary core-duo Dell desktop.

Susan Polgar, a former women’s world chess champion, and the eldest of the three Hungarian-Jewish Polgar sisters, describes the event on her popular blog. The comments to the blog entry show some difference of opinion:

Comment 1: “That’s not fair to the computer at all.”

Comment 2: “Big deal, Junior 10 vs. Junior 11 with a grandmaster moving the mouse….”

Visualization of Deep Junior Bxh2 sacrifice in the 5th game, New York, 2003.
Hmm… We need some perspective here. For that, let us take a few quick flashbacks, starting ca. 60 years ago with the pioneering efforts of Alan Turing, and especially Claude Shannon, who in 1950 wrote “Programming a Computer For Playing Chess“. In the article, Shannon lays out the foundations of computer chess, still practiced to this day: Given the current position where the computer must play a move, it will generate the tree of all hypothetical continuations: All moves playable at the position, then all possible replies to each of these moves, then all possible replies to the replies, and so on. Theoretically this process may continue indefinitely until a terminal position is reached, i.e. a checkmate, or a draw by the rules of chess. Unfortunately (or rather, fortunately) this possibility is merely theoretical, as the typical number of legal moves per position is around 40, and a chess game may last a hundred or so moves, the exponential explosion of possibilities forces a limit to the practical depth of the moves tree.

The Shannon trophy

Shannon proposed stopping the tree generation at some practical depth, and attaching an evaluation to the position at the leaf.

# Tel-Aviv’s “Jerusalem Beach”

## Friday’s evening at the beach

Late Friday afternoon, and the “Jerusalem beach” in Tel Aviv is still quite crowded with young and old people, families and singles, tourists, foreign workers and Israelis. The sea is calm and beautiful and the Tel Aviv shore landscape of people and buildings is restless and captivating. A young Philippine man with a baby on his shoulders ends a long cell phone conversation spoken in a strange language, with the familiar Hebrew ending “yalla bye“. A  father of a Russian speaking family takes pictures of his family with his cell phone, as does the father of an Arabic speaking family on our other side; in fact people all over the place are taking  pictures of each other with their cell phone cameras. What do they do with all these pictures? Where do they store them?

On our other side, another groups of foreign workes, six young women and two men. Two try to play beach paddle ball (matkot), a national Israeli beach game. They also take cell phone pictures, and then one plays the guitar and they all sing, “Jesus is our savior”, and “Jesus is our Shephard”, and even one song in Hebrew.

The sunset is breathtaking. A long waiting and then when the time comes the big orange sun disappears in a matter of seconds. Many people take sunset pictures with their cell phones.

On the way back we see three nuns with black outfits and one priest. They have serious expressions. They are Greek Orthodox, I think. The priest spins his hat in the air and tries to catch the hat with his head.

**************************************************

I have uploaded to the archive a paper on noisy quantum computation, which is a revision and an extension of my paper from 2006. A paper of Ehud Friedgut, Noam Nisan and myself about manipulations in voting rules was accepted to FOCS08. This is my 4th FOCS/STOC paper. (Larry Stockmeyer was a coauthor in one of my papers.)  I am planning to blog on issues around these two papers sometime in the future. (Meanwhile, there is an interesting post and discussion on quantum computers skepticism on Scott Aaronson’s blog.) Remember A. Nilli? We danced in her wedding on Sunday! Congratulations Nilli and John! As this post is launched I am at a high-dimensional phenomena conference in Sevillia. I have updated (or will soon update) the post about Han’s formula and provided more details. I also added a link to an interesting discussion on “Secret Blogging Seminar” related to my post “Is mathematics a Science”.

# Euler’s Formula, Fibonacci, the Bayer-Billera Theorem, and Fine’s CD-index

Bill Gessley proving Euler’s formula (at UMKC)

In the earlier post about Billerafest I mentioned the theorem of Bayer and Billera on flag numbers of polytopes. Let me say a little more about it.

## 1. Euler

Euler’s theorem asserts that for a 3-polytope P

### V-E+F=2.

The extension to d-dimensions asserts that for every d-polytope

### The Euler Relation: $f_0(P) - f_1(P) +F_2(P) + \dots + (-1)^d f_{d-1}(P) = 1 - (-1)^d.$

There were several incomplete proofs of Euler’s theorem in the late 19th century, but the first complete proof came via Poincare’s work in algebraic topology and the Euler-Poincare theorem. Later, simple geometric proofs were found and the gap in certain 19th theory proofs which relied on an unproved assumption of shellability was completed when Bruggesser and Mani proved in 1970 that the boundary of every d-polytope is shellable.

## 2. Fibonacci

Let’s move now to flag numbers. Consider a d-polytopes P. for a set $S \subset$ {-1,0,1,2,…,d-1,d}, $S=${ $i_1,i_2,\dots,i_k$} , $i_1, define the flag number $f_S$ as the number of chains of faces $F_1 \subset F_2 \subset \dots F_k$, where $\dim F_j=i_j$.  We will assume from now on that S contains both ‘-1′, and ‘d’. (Adding or deleting these entries from S does not change the value of the flag number.) Let $c_d$ be the dth Fibonacci number. ($c_1=1$, $c_2=2$, $c_3=3$, $c_4=5$, etc.)  Bayer and Billera proved:

### Theorem: the affine dimension of flag numbers of d-polytopes is $c_d-1$

There are many linear relations among the flag numbers that are implied by Euler’s theorem. For example: $f_{01}=2f_1$. This follows from the fact that every 1-polytope has 2 vertices. (This is Euler’s formula for dimension 1.) Another example: $f_{02}=f_{12}$. This follows from the fact that a polygon has the same number of vertices as edges which is Euler’s formula for d=2. Here are two, more complicated, examples: $f_{1569}=f_{1469}-f_{1369}+f_{1269}$ and $f_{1679}=f_{1579}-f_{1479}+f_{1379}-f_{1279}+2f_{179}$. Let’s understand the first of the two: Fix a flag of faces Continue reading

# Helly’s Theorem, “Hypertrees”, and Strange Enumeration II: The Formula

In the first part of this post we discussed an appealing conjecture regaring an extension of Cayley’s counting trees formula. The number of d-dimensional “hypertrees” should somehow add up  to $n^{{n-2} \choose {d}}$. But it was not clear to us which complexes we want to count and how. This counting problem started from a Helly type conjecture proposed by Katchalski and Perles.
For d=2 n=6 the situation was confusing. We had 46608 complexes that were collapsible. Namely, for these complexes it is possible to delete all triangles one at a time by removing in each step a triangle T and an edge E which is contained only in T. Once all triangles are removed we are left with a spanning tree on our 6 vertices. (Five out of the 15 edges survive).  In addition, there were 12 simplicial complexes representing 6-vertex triangulations of the real projective plane.
We will continue the discussion in this part, show how the conjecture can be saved and at what cost. We will also discuss the solution of the Perles-Katchalski conjecture –  a Helly’s type conjecture that we started with.   In the third part we will explain the proof and mention further related results and problems, discuss higher Laplacians and their spectrum, and mention a few related probabilistic problems.

### 8. How to make the conjecture work

With such a nice conjecture we should not take no for an answer. To make the conjecture work we need to count each of the twelve 6-vertex triangulations of the real projective plane, four times. Four is the square of the number of elements in $H_1(RP^2)$. This is the difference in higher dimensions, a Q-acyclic complex need not be Z-acyclic. Homology groups can have non trivial torsion.  In our case $H_{d-1}(K)$ can be a non trivial finite group.
Here is the theorem:

### $\sum |H_{d-1}(K,{\bf Z})|^2 = n^{{n-2} \choose {d}},$

where the sum is over all d-dimensional simplicial complexes K on n labelled vertices, with a complete (d-1)-dimensional skeleton, and which are Q-acyclic, namely all their (reduced) homology groups with rational coefficients vanish.
Looking at the various proofs of Cayley’s formula (there are many many many beautiful proofs and more), which one (or more) would you expect to extend to the high dimensional case? We will answer this question in part III. Can you guess? Continue reading

# Optimism – two quotes

1. Here is a quote from Karl Popper’s paper “Science, Problems, Aims, Responsibilities” about Francis Bacon: “According to Bacon, nature, like God, was present in all things, from the greatest to the least. And it was the aim or the task of the new science of nature to determine the nature of all things, or, as he sometimes said, the essence of all things. This was possible because the book of nature was an open book. All that was needed was to approach the Goddess of Nature with a pure mind, free of prejudices, and she would readily yield her secrets. Give me a couple of years free from other duties, Bacon somewhat unguardedly exclaimed in a moment of enthusiasm and I shall complete the task – the task of copying the whole Book of Nature, and of writing the new science.”

2. Here is a tale from Arundhati Roy’s book “The God of Small Things”.  In the book Margaret Kochamma tells the following joke to Chacko in Oxford, England, where the two meet: A man had twin sons… Pete and Stuart. Pete was an Optimist and Stuart was a Pessimist… On their thirteenth birthday their father gave Stuart – the Pessimist – an expensive watch, a carpentry set and a bicycle… And Pete’s – the Optimist’s – room he filled with horse dung… When Stuart opened his present he grumbled all morning. Continue reading

# Billerafest

I am unable to attend the conference taking place now at Cornell, but I send my warmest greetings to Lou from Jerusalem. The titles and abstracts of the lectures can be found here. Let me tell you about two theorems by Lou.

The first is the famous g-theorem: The g-theorem is a complete description of f-vectors (= vecors of face numbers) of simplicial d-polytopes. This characterization was proposed by Peter McMullen in 1970, and it was settled in two works. Billera and Carl Lee proved the sufficiency part of McMullen’s conjecture, namely for every sequence of numbers which satisfies McMullen’c conjecture they constructed a simplicial d-polytope P whose f-vector is the given sequence. Richard Stanley proved the necessity part based on the hard Lefschetz theorem in algebraic geometry. The assertion of the g-conjecture (the necessity part) for triangulations of spheres is open, and this is probably the one single problem I spent the most time on trying to solve.

The second theorem is a beautiful theorem by Margaret Bayer and Billera. Consider general d-polytopes. for a set $S \subset$ {0,1,2,…,d-1}, $S=${ $i_1,i_2,\dots,i_k$} , $i_1, define the flag number $f_S$ as the number of chains of faces $F_1 \subset F_2 \subset \dots F_k$, where $\dim F_j=i_j$.  Bayer and Billera proved that the affine dimension of flag numbers of d-polytopes is $c_d-1$ where $c_d$ is the dth Fibonacci number. ($c_1=1$, $c_2=2$, $c_3=3$, $c_4=5$, etc.) The harder part of this theorem was to construct $c_d$ d-polytopes whose sequences of flag numbers are affinely independent.  The construction is simple: It is based on polytopes expressed by words of the form PBBPBPBBBPBP  where you start with a point, and P stands for “take a pyramid” and B stands for “take a bipyramid.” And the word starts with a P (to the left) and has no two consecutive B’s.

Let’s practice the notions of f-vectors and flag vectors on the 24-cell   . (The figure is a 3-dimensional projection into one of the facets of the polytope.)

This  4-polytope has 24 octahedral facets. It is self dual.
So $f_0=f_3=24$. And $f_1=f_2=96$. And $f_{02}=288$, $f_{03}=192$, etc.

# Helly’s Theorem, “Hypertrees”, and Strange Enumeration I

### 1. Helly’s theorem and Cayley’s formula

Helly’s theorem asserts: For a family of n convex sets in $R^d$, n > d, if every d+1 sets in the family have a point in common then all members in the family have a point in common.

Cayley’s formula asserts: The number of  trees on n labelled vertices is $n ^{n-2}$.

In this post (in two parts) we will see how an extension of Helly’s theorem has led to high dimensional analogs of Cayley’s theorem.

left: Helly’s theorem demonstrated in the Stanford Encyclopedia of Philosophy (!), right: a tree

### 2. Background

This post is based on my lecture at Marburg. The conference there was a celebration of new doctoral theses Continue reading

# A Small Debt Regarding Turan’s Problem

Turan’s problem asks for the minimum number of triangles on n vertices so that every 4 vertices span a triangle. (Or equivalently, for the maximum number of triangles on n vertices without a “tetrahedron”, namely without having four triangles on four vertices.)  When we discussed Turan’s problem, we stated a lemma without giving the proof. Here is the proof.

Lemma: A three uniform hypergraph G on n vertices, so that every four vertices span a triangle satisfies:

$\dim H_1(K,F) \le n-2$.

Here, K is the simplicial complex on the n vertices which has all possible edges and, in addition, the triangles in G. F can be any field of coefficients, below we assume that F=Z/2. (But very little changes are required for the general case.)

Proof:  A little background: The space of 1-dimensional cycles of the complete graph with n vertices is of dimension ${n-1} \choose {2}$. Start with the star T where vertex ‘1’ is adjacent to all other vertices. every edge e={i,j} not in T, determines a cycle c(e) supported by the triangle {1,i} {1,j} and {i,j}. It is easy to see that all these cycles are linearly independent in the space of cycles of the complete graph and span this space.

Now to the proof itself. Let G be a hypergraph with the property that every 4 vertices span a triangle and let K be the 2-dimensional simplicial complex obtained by adding the triangles in G to the complete graph. $H_1(K)$ is still spanned by the cycles c(e) for all edges e={i,j} $1. Let H be a maximal set of edges e so that all the corresponding c(e) are linearly independent in $H_1(K)$. It suffices to prove:

Claim: H is a forest.