Monthly Archives: September 2008

Extremal Combinatorics III: Some Basic Theorems

Posted on September 28, 2008 by

. Shattering Let us return to extremal problems for families of sets and describe several basic theorems and basic open problems. In the next part we will discuss a nice proof technique called “shifting” or “compression.” The Sauer-Shelah (-Perles -Vapnik-Chervonenkis) Lemma: (Here we write .) … Continue reading →

Posted in Combinatorics, Open problems | Tagged , | 8 Comments

New Haven (mainly pictures)

Posted on September 25, 2008 by

]  Yale, New Haven   I am back in New Haven which have become my home away from home in the last five years.      Cappuccino’S and more – Cedar cross Congress, New Haven. Not only that this name is similar … Continue reading →

Posted in Uncategorized | Tagged , , , | Leave a comment

Annotating Kimmo Eriksson’s Poem

Posted on September 18, 2008 by

“Start counting her NUMBER OF FACES,” Kimmo Eriksson, Brush up your Björner (2008). The time is right to annotate Kimmo Eriksson’s memorable poem: 1. What are Chip firing games? Many women will find it admirable if you tell her she … Continue reading →

Posted in Combinatorics, Poetry | Tagged , , , , , , , , , , | 7 Comments

A Diameter Problem (5)

Posted on September 16, 2008 by

6. First subexponential bounds.  Proposition 1: How to prove it: This is easy to prove: Given two sets and in our family , we first find a path of the form where, and . We let with and consider the family … Continue reading →

Posted in Combinatorics, Convex polytopes, Open problems | Tagged | 1 Comment

Diameter Problem (4)

Posted on September 9, 2008 by

Let us consider another strategy to deal with our diameter problem. Let us try to associate other graphs to our family of sets. Recall that we consider a family of subsets of size  of the set . Let us now associate  … Continue reading →

Posted in Combinatorics, Convex polytopes, Open problems | Tagged | 1 Comment

Diameter Problem (3)

Posted on September 7, 2008 by

3. What we will do in this post and and in future posts We will now try all sorts of ideas to give good upper bounds for the abstract diameter problem that we described. As we explained, such bounds apply … Continue reading →

Posted in Combinatorics, Convex polytopes, Open problems | Tagged , , | 1 Comment

Oded

Posted on September 4, 2008 by

  I just heard the terrible news that Oded Schramm was killed in a hiking accident. Oded was hiking on Guye Peak near Snoqualmie Pass near Seattle. This is a terrible loss to Oded’s family, and our hearts and thoughts are … Continue reading →

Posted in Obituary | Tagged | 10 Comments

The Prisoner’s Dilemma, Sympathy, and Yaari’s Challenge

Posted on September 3, 2008 by

Correlation and Cooperation In our spring school devoted to Arrow’s economics, Menahem Yaari gave a talk  entitled “correlation and cooperation.” It was about games as a model of people’s behavior, and Yaari made the following points: It is an empirical fact … Continue reading →

Posted in Economics, Games, Philosophy, Rationality | Tagged , , | 2 Comments