REU 2005 · Discrete Mathematics · Lecture 1

Instructor: László Babai Scribe: Eric Purdy

July 18, 2005. Last revised July 19, 2005.

1 Lecture 1

1.1 Two-Distance Sets

Definition 1.1. A two-distance set in ℝ^{n} is a set of points {p_{1}, …, p_{m}} such that dist(p_{i}, p_{j}) ∈ {α, β} for i ≠ j. That is, the distance between any two distinct points in the set has one of two fixed values.

Some examples in the plane: an isosceles triangle, a square, a regular pentagon.

Exercise 1.2. Prove: In a regular pentagon, the ratio of a diagonal to a side is \frac{1+\sqrt{5}}{2}, the golden ratio.

Exercise 1.3. Prove that a two-distance set in ℝ^{2} has at most 5 points.

Similarly, we can define one-distance sets. In ℝ^{2}, an equilateral triangle is the only example of a one-distance set with three points. In ℝ^{3}, a regular tetrahedron is a onedistance set with four points. Similarly, the n-dimensional regular simplex is a one-distance set with n + 1 points in ℝ^{n}.

It is not immediate how to give coordinates for the regular simplex (an equilateral triangle with one side on the axis will have coordinates (0, 0), (1, 0), (\frac{1}{2}, \frac{\sqrt{3}}{2})), but there is a nice way to give its coordinates in ℝ^{n+1}. Take the standard basis vectors in ℝ^{n+1}, which have coordinates (1, 0, 0, …, 0), (0, 1, 0, …, 0), …, (0, 0, …, 0, 1). These all lie on the n-dimensional hyperplane given by the equation x_{1} + x_{2} + ⋯ + x_{n} = 1, which is isometric to ℝ^{n}. And the distance between any two of these points is \sqrt{2}, so this is in fact the n-dimensional regular simplex.

Now, we ask how many points a two-distance set in ℝ^{n} can have. We will denote this maximum number by m_{2}(n).

We can get n + 2 points by reflecting one vertex of the n-dimensional simplex across the plane of the rest of the vertices. We can get 2n by taking points of the form (0, …, 0, ±1, 0, …, 0) in ℝ^{n}. This will give us distances 2 and \sqrt{2}. This gives us a square in 2 dimensions, and in general it gives us the n-dimensional (hyper)octahedron.

Exercise 1.4. Find a two-distance set in ℝ^{n} with a quadratic number of points.

Theorem 1.5. m_{2}(n) ≤ \frac{(n+1)(n+4)}{2} ∼ \frac{n^{2}}{2} , where ∼ refers to asymptotic equality.

This theorem is asymptotically best possible, as a simple solution to the preceding exercise will show.

Proof. Let {x_{1}, …, x_{m}} ⊂ ℝ^{n} be a two-distance set. Let α,β be the two distances.

The distance between any two points x and y is the norm of their difference, i.e., dist(x, y) = ∥x − y∥ = \sqrt{∑_{i=1}^{n}(x_{i} − y_{i})^{2}}.

Note that, for fixed y, dist(y, z)^{2} = ∑_{i=1}^{n}(y_{i} − z_{i})^{2} is a polynomial in the coordinates of z.

Also, note that dist(x, y) = α ⟺ dist(x, y)^{2} − α^{2} = 0.

Now, for t ∈ ℝ^{n} let f_{i}(t) = (dist(x_{i}, t)^{2} − α^{2})(dist(x_{i}, t)^{2} − β^{2}). This is a polynomial in n variables. It will be zero when the distance between x_{i} and t is either α or β. Therefore, if the x_{i} form a two-distance set, we have

f_{i}(x_{j}) = \begin{cases}α^{2}β^{2} ≠ 0 & i = j \\ 0 & i ≠ j \end{cases}

Claim 1.6. The polynomials f_{i}(t) ∈ ℝ[t_{1}, …, t_{n}] are linearly independent over ℝ.

Proof. Suppose that some linear combination of the f_{i} is zero:

∑_{i=1}^{m} γ_{i}f_{i} = 0  (1.1)

We wish to show that each γ_{i} is zero.

We substitute x_{j} in this expression, and we get ∑_{i=1}^{m} γ_{i}f_{i}(x_{j}) = γ_{j}α^{2}β^{2} = 0. α^{2}β^{2} is nonzero, so we must have γ_{j} = 0 for all j. Therefore, the f_{i} are linearly independent, and the claim is proved.

Now, we want to prove that the f_{i} reside in some low-dimensional space, so we can take advantage of the following basic fact of linear algebra:

Fact 1.7. If f_{1}, …, f_{m} are linearly independent elements of a vector space, and each one is a linear combination of some elements g_{1}, …, g_{k}, then m ≤ k.

So, it remains to find a small set of polynomials in terms of which all the f_{i} can be expressed.

f_{i}(t) = (∥t − x_{i}∥^{2} − α^{2})(∥t − x_{i}∥^{2} − β^{2})  (1.2)
= (∑_{j=1}^{n}(t_{j} − x_{ij})^{2} − α^{2})(∑_{j=1}^{n}(t_{j} − x_{ij})^{2} − β^{2})  (1.3)

= (∑_{j=1}^{n} t_{j}^{2} − 2 ∑_{j=1}^{n} x_{ij}t_{j} + ∑_{j=1}^{n} x_{ij}^{2} − α^{2})(∑_{j=1}^{n} t_{j}^{2} − 2 ∑_{j=1}^{n} x_{ij}t_{j} + ∑_{j=1}^{n} x_{i}j^{2} − β^{2}) (1.4)

= (∥t∥^{2} + ∑_{j=1}^{n} a_{j}t_{j} + b_{1})(∥t∥^{2} + ∑_{j=1}^{n} a_{j}t_{j} + b_{2})  (1.5)

= ∥t∥^{4} + ∑_{j=1}^{n} 2a_{j}t_{j}∥t∥^{2} + ∑_{1≤j<k≤n} c_{jk}t_{j}t_{k} + ∑_{j=1}^{n} d_{j}t_{j} + e  (1.6)

Thus, each f_{i} is a linear combination of the following polynomials: ∥t∥^{4}, t_{j}∥t∥^{2} (1 ≤ j ≤ n), t_{j}t_{k} (1 ≤ j ≤ k ≤ n), t_{j} (1 ≤ j ≤ n), 1. There are 1 + n + (\binom{n}{2} + n) + n + 1 = \frac{(n+1)(n+4)}{2} of these polynomials, so by the basic fact of linear algebra, we have m ≤ \frac{(n+1)(n+4)}{2}, as stated.

Exercise 1.8. Generalize this argument to prove an upper bound on m_{s}(n), the maximum size of an s-distance set. An s-distance set in ℝ^{n} is a set of points {x_{1}, …, x_{m}}, with dist(x_{i}, x_{j}) ∈ α_{1}, …, α_{s} for i ≠ j. Show that for every fixed s, m_{s}(n) ∼ \frac{n^{s}}{s!} .

To do the previous exercise, you will need to do the following subexercise:

Exercise 1.9. Count the monomials of degree s in n variables. A monomial is a one-term polynomial with coefficient 1, like t_{1}^{3}, t_{1}^{2}t_{2} or t_{1}t_{2}t_{3}. The answer should be \binom{n+s−1}{s}.

1.2 Bollobás’s Problem

We have sets A_{1}, …, A_{m} and B_{1}, …, B_{m}, where for all 1 ≤ i, j ≤ m, |A_{i}| = r,|B_{i}| = s, and

|A_{i} ∩ B_{j}| = \begin{cases}= 0 & i = j \\ ≠ 0 & i ≠ j \end{cases} .

Let m(r, s) be the maximum m for a set-system satisfying these requirements.

For s = 1, we can achieve m = r + 1, by taking X = {p_{1}, …, p_{r+1}} to be a set with r + 1 elements, B_{i} = {p_{i}}, and A_{i} = X \ B_{i}. Therefore, m(r, 1) ≥ r + 1. To prove that m(r, 1) ≤ r + 1, note that each B_{i} is a single point, so that A_{1} ⊇ B_{2} ∪ ⋯ ∪ B_{m}. Therefore, A_{1} (and all other A_{i}) must contain m − 1 elements, so r = m − 1.

m(r, 2) ≥ \binom{r+2}{2} = \binom{r+2}{r}. Let the B_{i} be all the pairs from a set X with r + 2 elements, and let A_{i} = X \ B_{i}. Similarly, we get m(r, s) ≥ \binom{r+s}{s} by taking a universe of r + s elements, letting the B_{i} be all sets of size s, and letting A_{i} = X \ B_{i}.

Theorem 1.10 (Bollobás). (abridged) m(r, s) = \binom{r+s}{s}

The full version of this theorem will be stated next time.