Category Archives: Convexity

Igor Pak’s “Lectures on Discrete and Polyhedral Geometry”

pak3

Here is a link to Igor Pak’s  book on Discrete and Polyhedral Geometry  (free download) . And here is just the table of contents.

It is a wonderful book, full of gems, contains original look on many important directions, things that cannot be found elsewhere, and great beyond great pictures (which really help to understand the mathematics). Grab it!

 

pak1

Buffon’s Needle and the Perimeter of Planar Sets of Constant Width

Here is an answer to “Test your intuition (8)”. (Essentially the answer posed by David Eppstein.)

BuffonNeedle_700

(From Wolfram Mathworld)

Buffon’s needle problem asks to find the probability that a needle of length \ell will land on a line, given a floor with equally spaced parallel lines at distance one apart. The problem was posed by Georges-Louis Leclerc, Comte de Buffon (1707 – 1788).

There is a familiar computation showing that when \ell \le 1 the probability is 2\ell/\pi. A computation-free proof can be found in these pages on geometric probability written mostly by Molly McGinty. (They were pointed to me by Sergiu Hart.)

Briefly the computation-free argument goes as follows:

1) Consider the expected number of crossings of a needle with the lines rather than the probability of crossing.

2) Allow also polygonal needles.

3) Show, based on linearity of expectation, that for a polygonal needle the expected number of crossings is a linear function c\ell of the length \ell of the needle.

4) Consider now a circular needle of radius 1/2. Note that with probability one it has two crossings with the lines. Deduce that c=2/\pi.

This gives a proof for Buffon’s needle problem. But now consider any closed planar curve with constant width one. Again with probability one it will have two crossings with the parallel lines. Therefore, it has the same perimeter as the circle.

Update: The argument above Continue reading

Raigorodskii’s Theorem: Follow Up on Subsets of the Sphere without a Pair of Orthogonal Vectors

raigor

Andrei Raigorodskii

(This post follows an email by Aicke Hinrichs.)

In a previous post we discussed the following problem:

Problem: Let A be a measurable subset of the d-dimensional sphere S^d = \{x\in {\bf R}^{d+1}:\|x\|=1\}. Suppose that A does not contain two orthogonal vectors. How large can the d-dimensional volume of A be?

Setting the volume of the sphere to be 1, the Frankl-Wilson theorem gives a lower bound (for large d) of  1.203^{-d},
2) The double cap conjecture would give a lower bound (for large d) of 1.414^{-d}.

A result of A. M. Raigorodskii from 1999 gives a better bound of 1.225^{-d}. (This has led to an improvement concerning the dimensions where a counterexample for Borsuk’s conjecture exists; we will come back to that.) Raigorodskii’s method supports the hope that by considering clever configurations of points instead of just \pm 1-vectors and applying the polynomial method (the method of proof we described for the Frankl-Wilson theorem) we may get closer to and perhaps even prove the double-cap conjecture.

What Raigorodskii did was to prove a Frankl-Wilson type result for vectors with 0,\pm1 coordinates with a prescribed number of zeros. Here is the paper.

Now, how can we beat the 1.225^{-d} record???

Colorful Caratheodory Revisited

caratheodory-colored

 

Janos Pach wrote me:   “I saw that you several times returned to the colored Caratheodory and Helly theorems and related stuff, so I thought that you may be interested in the enclosed paper by Holmsen, Tverberg and me, in which – to our greatest surprise – we found that the right condition in the colored Caratheodory theorem is not that every color class contains the origin in its convex hull, but that the union of every pair of color classes contains the origin in its convex hull. This already guarantees that one can pick a point of each color so that the simplex induced by them contains the origin. A similar version of the colored Helly theorem holds. Did you know this?”

I did not know it. This is very surprising! The paper of Holmsen, Pach and Tverberg mentions that this extension was discovered independently by  J. L. Arocha, I. B´ar´any, J. Bracho, R. Fabila and L. Montejano.

Let me just mention the colorful Caratheodory agai. (we discussed it among various Helly-type theorems in the post on Tverberg’s theorem.)

The Colorful Caratheodory Theorem: Let S_1, S_2, \dots S_{d+1} be d+1 sets in R^d. Suppose that x \in conv(S_1) \cap conv (S_2) \cap conv (S_3) \cap \dots \cap conv (S_{d+1}). Then there are x_1 \in S_1, x_2 \in S_2, \dots x_{d+1} \in S_{d+1} such that x \in conv (x_1,x_2,\dots,x_{d+1}).

And the strong theorem is:

The Strong Colorful Caratheodory Theorem: Let S_1, S_2, \dots S_{d+1} be d+1 sets in R^d. Suppose that x \in conv(S_i \cup S_j)  for every 1 \le i <j \le d+1. Then there are x_1 \in S_1, x_2 \in S_2, \dots x_{d+1} \in S_{d+1} such that x \in conv (x_1,x_2,\dots,x_{d+1}).

Janos, whom I first met thirty years ago,  and who gave the second-most surprising introduction to a talk I gave, started his email with the following questions:

“Time to time I visit your lively blog on the web, although I am still not quite sure what a blog is… What is wordpress? Do you need to open an account with them in order to post things? Is there a special software they provide online which makes it easy to include pictures etc? How much time does it take to maintain such a site?”

These are excellent questions that may interest others and I promised Janos that I will reply on the blog. So I plan comments on these questions in some later post. Meanwhile any comments from the floor are welcome.

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