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.

Frankl-Rodl’s Theorem and Variations on the Cap Set Problem: A Recent Research Project with Roy Meshulam (A)

Voita Rodl

I would like to tell you about a research project in progress with Roy Meshulam. (We started it in the summer, but then moved to other things;  so far there are interesting insights, and perhaps problems, but not substantial results. Noga Alon contributed an important observation, and Jeff Kahn and Gabor Simonyi helpful comments.)  

Roy and I are friends and have been discussing various mathematical problems for decades. In the last few years we have studied together topological Helly-type theorems and have written several papers together. Our most recent success was finding a topological version of a Helly-type theorem by Nina Amenta. This post is on another problem.

As always, and more so in the spirit of Nielsen’s and Gowers’s recent suggestions:  comments, ideas, related problems, lemmas, and discussions  are welcome.  Links or references to earlier works (published and unpublished) are also welcome.  I thought to wait with this story after I discuss the Frankl-Wilson theorem and the Frankl-Rodl theorem in my extremal combinatorics series. But as this project is somewhat related to the density Hales-Jewett project discussed over Gowers’s blog (and even more to this thread at Tao’s blog), I decided to go ahead with it.

 

Part A: Finding generalized solutions for the cap set problem

1. Modular-lines-free-subsets

Let n=3m. A modular line in T(n)= \{0,1,2\}^n is a set of  three elements x,y,z such that the number of coordinates i for which x_i + y_i + z_i =a is zero modulo m for a=0,1,2. (The sum x_i+y_i+z_i is taken modulo 3.)

Problem 1:  How large can a subset F of T(n) be without containing a modular line? Prove that |F| < (3-\epsilon)^n, for some constant \epsilon >0.

2. Why? avoiding lines (3-term arithmetic progressions) in Z_3^n..

The following is a well-known problem:

Problem 2: Find the largest size f(n) of a set A \subset Z_3^n without an arithmetic progression of size 3. In this case an arithmetic progression of size three is simply a sequence of three elements x, y and z such that x+y+z=0. In other words, an arithmetic progression is simply an affine line.

This problem was discussed by Frankl, Graham, and Rodl in 1987 (and perhaps was posed even earlier) and they showed that f(n)=o(3^n). Roy Meshulam proved that f(n) \le 3^n/n. This is a beautiful and clear application of Roth’s argument (for his famous theorem on the density of sets without 3-term arithmetic progressions,) for the case of subsets of \{1,2,\dots,n\}. Ten years ago Roy and I tried quite hard to push this Fourier-theoretic argument and to get a better bound, even slightly, even very slightly. We did not succeed. (And so far, nobody else has; a recent impressive result of Tom Sanders for 3-term arithmetic progressions without a repeated element for subsets of  Z_4^n gives reason for optimism.) Let us write f(n)=3^n/g(n). The best lower bound on g(n) is n. There is a construction of Edell showing that f(n) \ge2.2^n and thus the best upper bound for g(n) is more than 1.3^n. The gap is huge! What is the true value? Terry Tao wrote a lovely post on this problem. A set in Z_3^n without a 3-term arithmetic progression (or alternatively not containing an affine line) is called a cap set.

Let me mention that the set of 0-1 vectors of length n is a very simple example of a cap set of size 2^n; choosing a set at random works if the size is less than 3^{n/3}.   Problem 1 is a variation on problem 2.  Continue reading

Colloquium at Berlin

I arrived to Berlin for a short visit to give a colloquium talk at the new BMS on Helly-type theorems, and to participate in the Ph. D. committee of  Ronald Wotzlaw. (Update: Dr. Ronald Wotzlaw.)

Here is an abstract for the talk decorated (it may take me a few days) with links to some earlier posts where matters are described in details, and also with some external links.

Helly’s theorem from 1912 asserts that for a finite family of convex sets in a d-dimensional Euclidean space, if every d+1 of the sets have a point in common then all of the sets have a point in common.
This theorem found applications in many areas of mathematics and led to numerous generalizations. Helly’s theorem is closely related to two other fundamental theorems in convexity: Radon’s theorem asserts that a set of d+2 points in d-dimensional real space can be divided into two disjoint sets whose convex hulls have non empty intersection. Caratheodory’s theorem asserts that if S is a set in d-dimensional real space and x belongs to its convex hull then x already belongs to the convex hull of at most d+1 points in S.

The first part of the lecture will discuss the basic relation between Helly, Radon, and Caratheodory’s theorems. Those are described in this post We move to discuss several quantitative generalizations of the theorem. At first we will consider what happens to the theorem if we replace the condition “non-empty intersection” by “the dimension of the intersection is at least r. (Question: What is the answer for r=1?)

Meir Katchalski settled this problem for every d and r Continue reading