Monthly Archives: February 2009

Ziegler´s Lecture on the Associahedron

Posted on February 28, 2009 by Gil Kalai

  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 … Continue reading →

Posted in Convex polytopes | Tagged , , , | 8 Comments

A Little More on Boolean Functions and Bounded Depth Circuits

Posted on February 24, 2009 by Gil Kalai

  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 … Continue reading →

Posted in Computer Science and Optimization | 7 Comments

Rosenfeld’s Odd-Distance Problem

Posted on February 21, 2009 by Gil Kalai

  Moshe Rosenfeld’s odd-distance problem: Let G be the graph whose vertices are points in the plane and two vertices form an edge if their distance is an odd integer. Is the chromatic number of this graph finite?  

Posted in Combinatorics, Open problems | 2 Comments

Which Coalition to Form (2)?

Posted on February 17, 2009 by Gil Kalai

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 … Continue reading →

Posted in Games, Rationality | Tagged | 5 Comments

Which Coalition?

Posted on February 16, 2009 by Gil Kalai

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 … Continue reading →

Posted in Games, Rationality | Tagged | 7 Comments

Basic Open Research and Failed Institutions – Imagine

Posted on February 12, 2009 by Gil Kalai

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 … Continue reading →

Posted in Economics, Rationality | Tagged | 5 Comments

Majority Rules! – The Story of Achnai’s Oven

Posted on February 10, 2009 by Gil Kalai

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 … Continue reading →

Posted in Rationality | 13 Comments

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

Posted on February 7, 2009 by Gil Kalai

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 … Continue reading →

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

Colloquium at Berlin

Posted on February 6, 2009 by Gil Kalai

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 … Continue reading →

Posted in Convexity, Updates | Leave a comment

The Hex-Voting-Rule (Not Recommended)

Posted on February 3, 2009 by Gil Kalai

Blue wins – if there is a right to left continuous path of blue regions Red wins – if there is north to south continuous path of red regions (A region is red or blue according to the majority of … Continue reading →

Posted in Economics, Games | 13 Comments