Fundamental Impossibilities

impossibilities

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

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 CO2 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

Lovasz’s Two Families Theorem

Laci and Kati

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 V_1,V_2,\dots V_t and W_1, W_2, \dots , W_t be two families of linear spaces having the following properties:

1) for every i, \dim V_i \le k, and \dim W_i \le \ell.

2) For every i, V_i \cap W_i = \{0\},

3) for every i \ne j, V_i \cap W_j \ne \{0\}.

Then t \le {{k+\ell} \choose {k}}.

This theorem is interesting even if all vector spaces are subspaces of an (k+\ell)-dimensional space.

Recall Bollobas’s two families theorem: Continue reading

Seven Problems Around Tverberg’s Theorem

bergen-2005-sinisa-helge-rade-imre

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 x_1,x_2,\dots, x_m be points in R^d, m \ge (r-1)(d+1)+1. Then there is a partition S_1,S_2,\dots, S_r of \{1,2,\dots,m\} such that \cap _{j=1}^rconv (x_i: i \in S_j) \ne \emptyset.

The (much easier) case r=2 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 A” by an arbitrary closure operation.

Let X  be a set endowed with an abstract closure operation X \to cl(X). The only requirements of the closure operation are:

(1) cl(cl (X))=cl(X) and

(2) A \subset B implies cl(A) \subset cl (B).

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

Eckhoff’s Partition Conjecture: For every closure operation t_r \le t_2 \cdot (r-1).

If X is the set of subsets of R^d and cl(A) is the convex hull operation then Radon’s theorem asserts that t_2(X)=d+1 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 A, denote by T_r(A) those points in R^d which belong to the convex hull of r pairwise disjoint subsets of X. We call these points Tverberg points of order r.

Conjecture (Kalai, 1974): For every A \subset R^d , \sum_{r=1}^{|A|} {\rm dim} T_r(A) \ge 0.

Continue reading

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 Q_n=[-\frac 12,\frac 12]^n\subseteq {\bf R}^n be the cube in {\bf R}^n centered at the origin and having n-dimensional volume equal to one.  What is the maximum (n-1)-dimensional volume M(d) of (H\cap Q_n) when H \subseteq {\bf R}^n is a hyperplane?

Can you guess the behavior of M(n) when n \to \infty? Can you guess the plane which maximizes the area of intersection for n=3?

Test your intuition before reading the rest of the entry.

Continue reading

Test Your Intuition (1)

Question:  Suppose that we sequentially place n balls into n 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 (1+o(1))\ln n/\ln \ln n 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.

Continue reading