Monthly Archives: February 2009

Ziegler´s Lecture on the Associahedron

j_stasheffdevadoss

 

The associahedron in 3 dimension, and James Stasheff. This picture is taken from Bill Casselman’s article on the associahedron. The article is entitled “Strange Associations” and starts with “There are many other polytopes that can be described in purely combinatorial terms. Among the more curious are the associahedra….”

Dov Tamari as a young student at the Hebrew University of Jerusalem.

The associahedron (also known as the Stasheff polytope) is a remarkable convex polytope first described combinatorially by James Stasheff in 1963. The first proof that it is indeed a polytope is attributed to John Milnor (unpublished). The combinatorial structure was considered independently by Dov Tamari who also asked for a realization as a convex polytope, and such a realization was found by Mark Haiman and Carl Lee. It was also constructed independently as a special case of a much more general construction (called ¨secondary polytopes¨) by Israel Gelfand, Michael Kapranov, and Andrei Zelevinsky.

These are lecture notes from Günter M. Ziegler´s lecture on the associahedron at the ¨DocCourse Combinatorics and Geometry 2009¨at CRM located at at the Autonomous University of Barcelona.

 zelevinsky

4.1 Making polytopes from graphs

We will start with several families of graphs and ask if there is a nice cell structure extending the graph structure, and if this cell structure is the cell structure of  a convex polytope. 

4.1.1 Permutations and the permutahedron

Example I:

The vertices: all permutations on the letters 1,2,… ,n

The edges: Two permutations are adjacent if one is obtained by the other by replacing the location of two adjacent letters.

The number of vertices is n!. The degree of every vertex is n-1.

4.1.2 Bracketing and the associahedron

(or triangulation of polygons with non-crossing diagonals, or binary trees)

Example II:

The vertices correspond to all ways to put brackets in an expression x_1x_2\cdots x_n of n non associative variables.

For example for 4 variables there are 5 vertices corresponding to: ((xy)z)u, (x(yz))u, (xy)(zu), x((yz)u), and x(y(zu)).  Those are in one to one correspondence with all possible triangulations of a 5-gon with noncrossing diagonals, as well as with binary trees with 4 leaves.

The edges are obtained by replacing a subword t(su) by (ts)u.

Note: “subword” of course means that t or s or u could be a word, not just a letter.

The number of vertices is the (n-1)-th Catalan number c_{n-1}=\frac{1}{n}{{2n-2} \choose {n-1}}. The degree of every vertex is n-1.

 4.1.3 Bracketing plus cyclic permutations and –  the cyclohedron

Raoul Bott in 1986

  

Example III:

The vertices: This time you consider all ways to put brackets in a word x_1x_2\cdots x_n as in example II and also in all words obtained as cyclic permutations of this word.

The edges: In addition to the same brackets as in example II you also allow changing the order of terms in the ¨top¨multiplication.

For example, when there are four variables we have 20 vertices. In addition to the type of edges we saw in the associahedron there is an edge also between (xy)(zu) to (zu)(xy) and between ((xy)z)u to u((xy)z).  

Continue reading

A Little More on Boolean Functions and Bounded Depth Circuits

 

Boolean circuits

This post (in a few parts) contains a quick introduction to Boolean circuits. It is related to the recent news post about the solution of Braverman to the Linial-Nisan conjecture. In particular, we will describe very quickly a formulation of the NP \ne P problem and discuss some issues about bounded depth circuits.  I hope that this gives a nice introduction to this area for non-experts (written also by a non-expert). Any comments and corrections (especially from experts!) are welcome. I want to mention, in particular, a result by  Benjamin Rossman about finding cliques in graphs for bounded depth circuits that I found exciting.

A. Boolean functions, Boolean circuits and the NP versus P problem.

1. Boolean functions

A Boolean function of n variables is simply a function f(x_1,x_2,\dots,x_n) where the variables x_k take the values +1 and -1 and the value of f itself is also either +1 and -1.

2. Boolean circuits

A Boolean circuit is a gadget that computes Boolean functions. Continue reading

Which Coalition to Form (2)?

Yair Tauman

(This post is a continuation of this previous post.)

Aumann and Myerson proposed that if political and ideological matters are put aside, the party forming the coalition would (or should) prefer to form the coalition in which its own power (according to the Shapley-Shubik power index) is maximal. They expected that this idea would have some predictive value  —  even in reality, where political and ideological considerations are of importance. A few days ago Yair Tauman, another well-known Israeli game theorist, mentioned on TV this recipe as a normative game-theoretic recommendation in the context of the recent Israeli elections. (For Yair’s analysis see also this article. (I even sent a critical comment.))

Over the years, Aumann was quite fond of this suggestion and often claimed that in Israeli elections it gives good predictions in some (but not all) cases. The original paper mentions the Israeli 1977 elections and how delighted one of the authors was that four months after the elections a major “centrist” party joined the coalition, leading to a much better Shapley value for the party forming the coalition.

I was quite skeptical about the claim that the maximum-power-to-the-winning-party rule has any predictive value and in 1999 with the help of Sergiu Hart I decided to test this claim. I asked Aumann which Israeli coalition he regards as fitting his prediction the best. His answer was the 1988 election where Shamir’s party, the Likud, had a very large Shapley value in the coalition it formed. We checked how high the Shapley value was compared to a random coalition that the winning party could have formed. Continue reading

Which Coalition?

The problem.

OK, we had an election and have a new parliament with 120 members. The president has asked the leader of one party to form a coalition. (This has not happened yet in the Israeli election but it will happen soon.) Such a coalition should include parties that together have more than 60 seats in the parliament.

Can game theory make some prediction as to which coalition will be formed or give some normative suggestions on which coalition to form?

Robert Aumann and Roger Myerson made  (in 1977) the following concrete suggestion.  (Update: A link to the full 1988 paper is now in place.)  The party forming the coalition would (or should) prefer to form the coalition in which its own power (according to the Shapley-Shubik power index) is maximal. Of course Continue reading

Basic Open Research and Failed Institutions – Imagine

Imagine if in the last ten years before the collapse, the huge failed financial and insurance institutions had had independent research units devoted to doing basic, open, and critical research on matters of relevance to the business, ethics, and future of these institutions. Might it have made a small difference for the better regarding the fate of these institutions?

 

[Full disclosure:] I make my living by doing basic research.

Majority Rules! – The Story of Achnai’s Oven

It is election day in Israel, and an opportunity to tell the beautiful and moving story of Achnai’s oven. 

Towards the end of the first century, a few decades after the big Jewish rebellion against the Romans, the sages of the “Sanhedrin” (The highest court in Jewish law) had to determine whether a certain oven “the oven of Achnai” is appropriate to use according to the Jewish law.

With the exception of one sage, Rabbi Eliezer, all sages declared that the oven can become ‘impure’ and therefire it is not appropriate for use.

Rabbi Eliezer who was convinced that his position was right declared:   “If the rule is as I say [That Achnai’s oven is in fact pure], then let this carob tree prove it!” Then the carob tree flew out of the ground and landed thirty yards away.

The sages were not impressed: “One does not bring evidence from the carob tree!”

Rabbi Eliezer continued: “If the rule is as I say, then let the stream of water prove it.”  And the stream of water flowed backwards.

“One does not bring evidence from a stream of water,” replied the other sages.

“If the rule is as I say then let the walls of this house  prove it!” continued Rabbi Eliezer, and the walls began to fall inward.  Rabbi Yehoshua, Eliezer’s main opponent, censored the walls for their interference and they did not fall but neither did they return to their previous position.

“If the law is as I say then let it be proved by Heaven,” continued Rabbi Eliezer and indeed a voice from Heaven came and asserted that Rabbi Eliezer was right! Rabbi Yehoshua stood up and said (quoting Deuteronomy 30:12) “It is not in Heaven, ” (לא בשמיים היא) and a later sage explained further (quoting Exodus 23:2): “it is for the majority to decide!” (כי אחרי רבים להטות). And so it was.