An Understanding of our fundamental limitations is among the most important contributions of science and of mathematics. There are quite a few cases where things that seemed possible and had been pursued for centuries in fact turned out to be fundamentally impossible. Ancient geometers thought that any two geometric lengths are commensurable, namely, measurable by the same common unit. However, for a right triangle with equal legs, the leg and the hypotenuse are incommensurable. In modern language (based on the Pythagorean theorem), this is the assertion that the square root of two is not a rational number. This was a big surprise in 600 BCE in ancient Greece (the story is that this discovery, attributed to a Pythagorean named Hippasus, perplexed Pythagoras to such an extent that he let Hippasus drown). Two centuries later, Euclid devoted the tenth book of his work *The* *Elements* to irrational quantities. The irrationality of the square root of 2 is an important landmark in mathematics. Similarly, the starting point of modern algebra can be traced back to another impossibility result. Algebraists found formulas for solving equations of degrees two, three, and four. Abel and Galois proved Continue reading

# Monthly Archives: December 2008

# Debates

Debates are fascinating human activities that are a mixture of logic, strategy, and show. Not everybody shares this fascination. The German author Emil Ludwig considered debates to be the death of conversation. Jonathan Swift regarded debates as the worst sort of conversation**, **and debates portrayed in books as the worst sort of reading. Public debates pose various interesting dilemmas. Continue reading

# Controversies In and Near Science

Controversies and debates in and around science – between researchers within the same discipline, between competing theories, between competing fields, and between accepted scientific viewpoints and viewpoints rooted outside science – are common.

Is there global warming and is it caused by high emissions of CO_{2} by humans? Or is global warming perhaps a myth, or rather an established fact caused by changes in the sun’s radiation, which has little to do with us? Is quantum physics correct? Can quantum computers, which have superior computation power that can crack the codes used for most commercial communication, be built? Are the teachings regarding free-market economy scientifically based? What is rationality? What is the weight of psychology in understanding economics? What is the value of mathematical tools in the social sciences? What are the limits of artificial intelligence? Is string theory promising as the ultimate physics theory of everything?

What is the origin of the Scrolls of Qumran (the Dead Sea scrolls)? Were they written by a sectarian group living in a village close to the caves where they were discovered, as the dominant theory asserts? Magen Broshi, a senior Jerusalem-based archaeologist and the ex-curator of the “Shrine of the Book” who subscribes to the central theory regarding the scrolls, said once in a public lecture: “There are twelve theories regarding the origins of the Qumran scrolls. Continue reading

# Lior, Aryeh, and Michael

Three dear friends, colleagues, and teachers Lior Tzafriri, Aryeh Dvoretzky and Michael Maschler passed away last year. I want to tell you a little about their mathematics.

** Lior Tzafriri** ( 1936-2008 )

Lior Tzafriri worked in functional analysis.

# Lovasz’s Two Families Theorem

**Laci and Kati**

This is the first of a few posts which are spin-offs of the extremal combinatorics series, especially of part III. Here we talk about Lovasz’s geometric two families theorem.

## 1. Lovasz’s two families theorem

Here is a very beautiful generalization of the two families theorem due to Lovasz. (You can find it in his 1977 paper Flats in Matroids and Geometric Graphs.)

**Lovasz’s Theorem:** Let and be two families of linear spaces having the following properties:

1) for every , , and .

2) For every , ,

3) for every , .

Then .

This theorem is interesting even if all vector spaces are subspaces of an -dimensional space.

Recall Bollobas’s two families theorem: Continue reading

# Seven Problems Around Tverberg’s Theorem

**Imre Barany, Rade Zivaljevic, Helge Tverberg, and Sinisa Vrecica**** **

Recall the beautiful theorem of Tverberg: (We devoted two posts (I, II) to its background and proof.)

**Tverberg Theorem (1965): **Let be points in , . Then there is a partition of such that .

The (much easier) case of Tverberg’s theorem is **Radon’s theorem**.

## 1. Eckhoff’s Partition Conjecture

Eckhoff raised the possibility of finding a purely combinatorial proof of Tverberg’s theorem based on Radon’s theorem. He considered replacing the operation : “taking the convex hull of a set ” by an arbitrary closure operation.

Let be a set endowed with an abstract closure operation . The only requirements of the closure operation are:

(1) and

(2) implies .

Define to be the largest size of a (multi)set in which cannot be partitioned into parts whose closures have a point in common.

Eckhoff’s Partition Conjecture: For every closure operation

If is the set of subsets of and is the convex hull operation then Radon’s theorem asserts that and Eckhoff’s partition conjecture would imply Tverberg’s theorem. Update (December 2010): Eckhoff’s partition conjecture was refuted by Boris Bukh. Here is the paper.

## 2. The dimension of Tverberg’s points

For a set , denote by those points in which belong to the convex hull of pairwise disjoint subsets of . We call these points **Tverberg points of order** .

Conjecture (Kalai, 1974):For every , .

# Michal Linial: Vive La Technology

- Nebi Samuel

It was a long night after crossing the Atlantic. I got to the airport and indeed the big signs of ‘Welcome’ and “TAAM SHEL BAIT” (taste of home) had a special appeal. It was 3:30 in the morning when I took the Taxi. The driver was very talkative and wanted to know where I am coming from, are the stories that he had heard on America true. Specifically he wanted to know if I went to the Twins to see the city from the tallest buildings etc, etc.

I replied shortly: “Yes, New York is as everybody said”. For the Twins, I replied: “No, there is no elevator there anymore”… I tried to be polite but at the same time to keep our touristy discussion to a minimum. The Taxi driver turned out to be quite sensitive to my poor situation and told me very proudly: “Please tell me where, and I will take you, I have a new GPS, just tell me the address and the GPS will show me the way”. Indeed, I shared with him the importance of the GPS technology and even told him that I may soon buy one for my own car. My address is Nave Sha’anan 18, I told him, and 2 minutes later, I was asleep, this time very confident that in 45 min I am at home and to my bed. The next thing I know is Continue reading

# 1:0 to Italy: Michal Linial

Coming back from Hinxton, the most exciting genome center in the world and the most boring place after 5pm… At 5:30, a shuttle bus takes all the ‘workers’ to the big city – to Cambridge. The shuttle bus dropped us in the middle of town and without noticing, I remained alone. I quickly looked around; actually, there was no one on the street… OK I decided, the evening is not lost yet, I will go to London…

I waited 5 minutes and a Taxi stopped next to me. To the train station” I said. My taxi driver started the ride and then slowed down, stopped for a minute next to an open bar looked extremely worried and after 2 minutes speeded up again. We moved another 100 meters and again, he slows down and stop for 2 minutes next to a TV screen in the next open bar. He looks bothered and mumbled to himself, I hate him, Continue reading

# Test Your Intuition (2)

**Question:** Let be the cube in centered at the origin and having -dimensional volume equal to one. What is the maximum -dimensional volume of when is a hyperplane?

Can you guess the behavior of when ? Can you guess the plane which maximizes the area of intersection for ?

Test your intuition **before** reading the rest of the entry.

# Test Your Intuition (1)

**Question:** Suppose that we sequentially place balls into boxes by putting each ball into a randomly chosen box. It is well known that when we are done, the fullest box has with high probability balls in it. Suppose instead that for each ball we choose **two** boxes at random and place the ball into the one which is less full at the time of placement. What will be the maximum occupancy?

Test your intuition **before** reading the rest of the entry.