# The Generation Gap

Which is larger, the generation gap between you and your perents or the generation gap between you and your children?

# A Problem on Planar Percolation

Conjecture (Gady Kozma):  Prove that the critical probability for planar percolation on a Cayley graph of the group $Z^2$ is always an algebraic number.

Gady  mentioned this conjecture in his talk here about percolation on infinite Cayley graphs.  (Update April 30: Today Gady mentioned to me an even bolder question: to show that for every group $\Gamma$, either all critical probabilities of its Cayley graphs are algebraic, or none is!!;  I recall a similarly bold conjecture regarding the property of being an expander which turned out to be false but was fruitful nevertheless.)

# A Conference and a School on Oded Schramm’s Mathematics

There will be a conference this summer in Redmond and a school in December in Jerusalem devoted to Oded Schramm’s mathematics.

## Redmond WA, August 30-31, 2009

To be held at Microsoft Research.

Here are links to the conference page and conference poster

Speakers include

 Omer Angel (University of British Columbia) Itai Benjamini (Weizmann Institute) Mario Bonk (University of Michigan) Michael Freedman (Microsoft Station Q) Christophe Garban (ֹcole Normale Supיrieure) Olle Haggstrom (Chalmers University of Technology) Zheng-Xu He (Beijing CAS Institute of Mathematics) Gregory F. Lawler (University of Chicago) Russell Lyons (Indiana University) Assaf Naor (New York University) Yuval Peres (Microsoft Research) Gabor Pete (University of Toronto) Steffen Rohde (University of Washington) Scott Sheffield (Massachusetts Institute of Technology) Stanislav Smirnov (Universitי de Genטve) Wendelin Werner (Universitי Paris-Sud XI) David B. Wilson (Microsoft Research)

## Jerusalem, 15-23 December 2009

To be held at the Hebrew University of Jerusalem, the Institute for Advanced Study, Feldman Building Givat Ram Campus. Continue reading

# The Intermediate Value Theorem Applied to Football

My idea (in my teenage years) of how to become a professional basketball player was a bit desperate. To cover for my height and my athletic (dis)abilities, I would simply practice how to shoot perfectly from every corner of the court. I would not have to run or jump. My team could pass the ball to me at the right moment and I would shoot. (I was a little worried that once I mastered this ability they would change the rules of the game.)

But this idea did not work. As much as I practiced, I could not shoot perfectly from all corners of the court, and not even from the usual places. In fact, my shooting was below average (although not as much below average as my other basketball skills.)

Next came my idea how to become a professional football (soccer) player. This idea was based on mathematics, an area where I had some advantage over other ambitious sports people; more precisely, my idea was based on the intermediate value theorem. (We had a post about this theorem.)

The idea is this: If you put a football on your head and start running the ball will fall from behind. But if you put the ball on your forehead and start running the ball will fall in front of you. By the intermediate value theorem, there must be a point, in between, such that if you run with the ball at this point, the ball will not fall at all. In fact you can find such a point for every way you would like to run. And you can even learn to adjust it if you change your route!  The plan was now simple. At the right moment I would get the ball from my team, put it on the right point on my forehead  start running and slalom my way towards the goal. (I was a little worried that once I mastered this ability they would  change the rules of the game.) I practiced it for several weeks, Continue reading

# Two Fractal Vegtables Found on Blogs

Physicists and mathematicians think alike:

From Kowalski’s blog

From asymptotia

# Exciting New Blogs and New Posts

There are new exciting blogs and all sort of nice things on old blogs. In Avzel’s journal you can find a post with the words and a link to the performence of a beautiful Leonard Cohen’s song “everybody knows”;  and you can find there as well as on Computational Complexity links to some great songs of Tom Lehrer. Noam Nisan (who encouraged me to start this blog) has now a blog of his own called “Algorithmic game theory” of with interesting posts on the econ-CS interface. One post is about Fourier theoretic proof of Arrow’s theorem and the recent paper by Noam, Ehud Friedgut and me on Quantitative Gibbard Satterthwhaite theorem.  (BTW, are you aware of blogs devoted to learning?, or to mathematical programming/optimization?) Dick Lipton has a new blog  called “Godel’s lost letter and P=NP,” where he covers in a very very nice style, the major developements that occured in theoretical computer science, (and from time to time outside it,) and the people that were involved in these developements. There is a spirit of light skepticism regarding the common wisdom about some of the central problems in some of the posts. This reminds me that scientific skepticism and how it should be practiced (if at all) is a great topic for discussion. Economist Al Roth has an extremely prolofic blog called “Market design.” Roth have created (with the help of Aaron his son,) very eraly on (in 1995,) a scientifically useful home page. And finally Terry Tao had a beautiful post on sailing into the wind in higher speed than the wind. And post-finally Scott Aaronson, breaks yet again new grounds, and asks four questions for Passover about corn, rice, and wheat.

And Frank Morgan (whom both me and Noga TA’d in Calculus 18.001  18.011 in 1983) has a lovely post on optimal paths in Baseball based on work with  Davide Carozza and  Stewart Johnson, and Jeff Elly has an econ blog with the good name “cheap talk”. And here is an excellent post on the 15 greatest statisticians by Yosi Levy (in Hebrew).

And Terry Tao illuminatingly rescaled the US budget to match incomes and expenses of a single family.

# (Eran Nevo) The g-Conjecture II: The Commutative Algebra Connection

Richard Stanley

This post is authored by Eran Nevo. (It is the second in a series of five posts.)

## The g-conjecture: the commutative algebra connection

Let $K$ be a triangulation of a $(d-1)$-dimensional sphere. Stanley’s idea was to associate with $K$ a ring $R$, and study the relations between algebraic properties of $R$ and combinatorial properties of $K$.

### Face ring

Fix a field $k$. The face ring (Stanley-Reisner ring) of $K$ over $k$ is $k[K]=k[x_{1},..,x_{n}]/I_{K}$ where $I_{K}$ is the homogenous ideal generated by the monomials whose support is not in $K$, $\{\prod_{i\in S}x_i:\ S\notin K\}$. For example, if $K$ is the boundary of a triangle, then $k[K]=k[x,y,z]/(xyz)$. $k[K]$ is graded by degree (variables have degree one, $1$ has degree zero), and let’s denote the degree $i$ part by $k[K]_i$. This part is a finite dimensional $k$-vector space and we can collect all these dimensions in a sequence, or a series, called the Hilbert series of $k[K]$, which carries the same information as $f(K)$. More precisely,

$hilb(k[K]):=\sum_{i\geq 0}\dim_k k[K]_i t^i = \frac{h_0(K)+h_1(K)t+...+h_d(K)t^d}{(1-t)^d}$

(recall that $K$ is $(d-1)$-dimensional).

### Cohen-Macaulay (CM) ring

The ring $k[K]$ is called Cohen Macaulay (CM) if there are $d$ elements $\Theta=\{\theta_1,..,\theta_d\}$ in $k[K]_1$ such that $k[K]$ is a free $k[\Theta]$-module. As $hilb(k[\Theta])=\frac{1}{(1-t)^d}$, the numerical consequence is that $hilb(k[K]/(\Theta))=h(K)$ (we use $h$ both as a vector and as a polynomial, with the obvious identification).

Macaulay (revisited) showed that the Hilbert series of standard rings (=quatient of the polynomial ring by a homogenous ideal) are exactly the $M$-vectors (sequences).

A theorem of Riesner characterizes the simplicial complexes $K$ with a CM face ring over a fixed field $k$ in terms of the homology of $K$ and its face links (with $k$-coefficients). It follows that if $K$ is a simplicial sphere then $k[K]$ is CM, hence $h(K)$ is an $M$ vector! This gives more inequalities on $f(K)$. This is also how Stanley proved the Upper Bound Conjecture, for face number of spheres: It follows that if $K$ is a $(d-1)$-sphere with $n$ vertices, and $C(d,n)$ is the boundary of the cyclic $d$-polytope with $n$ vertices, then for every $i$, $f_i(K)\leq f_i(C(d,n))$. This is as $h_i(K)\leq \binom{n-d+i-1}{i}=h_i(C(d,n))$.

### Hard Lefschetz

Let $K$ be the boundary of a simplicial $d$-polytope. Stanley observed that the hard Lefschetz theorem for toric varieties, an important theorem in algebraic geometry, translates in the language of face rings as follows: there exists $\Theta$ as above and $\omega\in k[K]_1$ such that the maps

$w^{d-2i}: (k[K]/(\Theta))_i\rightarrow (k[K]/(\Theta))_{d-i}$

are isomorphisms between those vector spaces for any integer $0\leq i\leq \frac{d}{2}$. In particular, $w: (k[K]/(\Theta))_{i-1}\rightarrow (k[K]/(\Theta))_{i}$ is injective for $1\leq i\leq \frac{d}{2}$. Thus, the quotient ring $k[K]/(\Theta, \omega)$ has Hilbert series starting with $g(K)$. This means, again by Macaulay theorem, that $g(K)$ is an $M$-vector!

Later, in 1993, McMullen gave a different proof of this part of his conjectured $g$-theorem. His proof actually proves hard Lefschetz for this case. See McMullen’s survey paper `Polyhedra and polytopes: algebra and combinatorics’.

### Problems

Does hard Lefschetz theorem hold for non polytopal spheres?

Can you think of examples of simplicial spheres which cannot be realized as the boundary of convex polytopes?

# Coffee, Cigarettes, and Aggression

Getting an upgrade to business class on a flight to Amsterdam en route to NYC seemed splendid. But I soon discovered that I was upgraded to one of the two rows for business smokers.

### The person on my left

The person to my left smoked Camel cigarettes. He had a pack of cigarettes on his table and he smoked a cigarette every 20 minutes. It was disturbing and I considered asking him not to smoke. But this was his right! He bought a business class ticket to the smoking section. I was just an upgrade, but even as a full-fledged businessman I would not have had the right to ask him not to smoke.

### An idea

I had another idea. When breakfast was served I had a cup of coffee on my tray, and the pack of Camel cigarettes was on my neighbors’s tray bordering mine. If I were to accidentally spill all my coffee on his pack, this may take the cigarettes out of action!

It was not an easy decision. Will it work? Is it morally justified?  Continue reading

# How the g-Conjecture Came About

This post complements Eran Nevo’s first  post on the $g$-conjecture

### 1) Euler’s theorem

Euler

Euler’s famous formula $V-E+F=2$ for the numbers of vertices, edges and faces of a  polytope in space is the starting point of many mathematical stories. (Descartes came close to this formula a century earlier.) The formula for $d$-dimensional polytopes $P$ is

$f_0(P)-f_1(P)+f_2(P)+\dots+(-1)^{d-1}f_{d-1}(P)=1-(-1)^d.$

The first complete proof (in high dimensions) was provided by Poincare using algebraic topology. Earlier geometric proofs were based on “shellability” of polytopes which was only proved a century later. But there are elementary geometric proofs that avoid shellability.

### 2) The Dehn-Sommerville relations

Dehn

Consider a 3-dimensional simplicial polytope, – Continue reading