A Conversation

There is a mathematical conversation about complexity lower bounds here:

http://gowers.wordpress.com/2009/09/22/a-conversation-about-complexity-lower-bounds/

It is related to one of the possible polymath projects mentioned in the post of the 17th.

Speech about mathemtatics and the internet

There is a text of a speech on the impact of internet based technology on academia at Terence Tao’s blog. It includes some discussion of the polymath projects and collaborative mathemtics. Here is the url:

http://terrytao.wordpress.com/2009/09/17/a-speech-for-the-american-academy-of-arts-and-sciences/

Post on future Polymath projects

There is a post “Possible future Polymath projects” at

http://gowers.wordpress.com/2009/09/16/possible-future-polymath-projects/

In it several future polymath projects are discussed.

Radon related problem 7

Let us generalize this problem to r sets:

We have 3r + 2 points on the plane. We want to show that we can divide them into r sets of three points and one set of two points such that the intersection of the convex hulls of all r sets is not empty.

We take 3r+1 of the points and apply Tverberg’s theorem.
It gives us r disjoint nonempty sets which together contain all 3r+1 points. The intersection of the convex hulls of these sets is nonempty. Let on of the points in the intersection of the convex hulls be x.

If any of the four sets are bigger than 3 then by Caratheodory’s theorem there is a three point subset that contains x. We take that as the new set in place of the four point set and add the additional point to a set less than three. We repeat this process untill all of the sets are three or less. Then we add the remaining point to a set with two points or less. The result is 3r+2 points divided into r sets of three or less. The only way to do this is r sets of three points and one set of two points which gives the desired theorem.

We can add more points and keep the distribution even since adding a point to a set of points increases the convex hull so the intersection of convex hulls still contains x. So we have the following if we have 3r+2 points or more we can divide them into r nonempty sets, the size of each set differing by at most one element from each other set such that the intersection of the convex hulls of the sets is nonempty.

In the next of this series of posts I want to look at higher dimensional spaces than the plane.

Radon related problem 6

Let us look at this version of the original problem in which the number of sets is increased by one:

We have 11 points on the plane. We want to show that we can divide them into three sets of three points and one set of two points such that the intersection of the convex hulls of all four sets is not empty.

We take 10 of the points and apply Tverberg’s theorem.
It gives us four disjoint nonempty sets which together contain all 10 points. The intersection of the convex hulls of these sets is nonempty. Let on of the points in the intersection of the convex hulls be x.

If any of the four sets are bigger than 3 then by Caratheodory’s theorem there is a three point subset that contains x. We take that as the new set in place of the four point set and add the additional point to a set less than three. We repeat this process untill all of the sets are three or less. Then we add the 11th point to a set with two points or less. The result is 11 points divided into four sets of three or less. The only way to do this is three sets of three points and one set of two points which gives the desired theorem.

Radon related problem 5

Let us look at ways this problem can be generalized. If we stay with three colors then we can add any additional points to the groups of two triangles and one line at will since adding a point to a convex hull will make it bigger we will still have nonzero intersection for the three sets. In particular we will have for any integer n greater than seven will have a division of n into three parts with any two parts differing in cardinality by at most one.

The next step would be to increase the number of colors and try to get a similar result. The next Tverberg result is that if we have 10 points in a plane and we divide them into four nonempty sets then the intersection of the convex hulls of the sets is nonempty. So the next step is to look at this result and try to proceed as we did in the case of three colors. I hope to do this in the next of this series of posts.