Pigeonhole constructions

From TheTangentSpace

The pigeonhole principle can be exemplified by the idea that, if we have 100 holes and 101 pigeons in the holes, there must be at least one hole with 2 pigeons. Here we'll explore a variation of this principle to show the existence of certain sets or other general objects. These ideas were motivated by a post on Timothy Gower's blog.

A motivating example

Does there exist a dense set of points $S\subset\mathbb{R}^2$ such that no two triangles in $S$ are similar? Yes.

How can we be sure? Just build one, one point at time. The set $\mathbb{Q}^2$ is dense in $\mathbb{R}^2$ , and the set $A := \mathbb{Q}\times\mathbb{Q}^2$ is countable. We can pick three starting points at random, and then iterate over $(r, x)\in A$ to add a new point to our set which is within distance $r$ of $x$ , yet does not introduce any similar triangles to our set.

This page is about generalizing this type of construction, which has been outlined in Gower's post, and was hinted at by an earlier blog post.

The existence theorem

Our framework will take four main parameters:

$X$ , the universe from which we build a subset (such as $\mathbb{R}^2$ )
$A$ , the set over which we require certain existence properties (such as an iterator of density)
$P (a, x)$ , the property required for element $a\in A$ and subset $x\subset X$ (such as $x$ containing a point within a neighborhood indicated by $a$ )
$Q (x)$ , the property excluded for subset $x\subset X$ (such as excluding similar triangles)

Suppose $A$ is well ordered by $<$ .

Notation: We'll write ${ < a}$ to denote the set of elements preceding $a$ in the well order. Given $T\subset X$ and $x\in X$ , we'll write $T + x$ to denote $T\cup\{x\}$ .

The following definitions use our four parameters $X, A, P$ , and $Q$ . Suppose we have a particular element $a\in A$ and a subset $T\subset X$ .

Definitions

Let $\mathsf{required}(a,T) := \{x\in X\setminus T| P(a, T+x)\}$ .
Let $\mathsf{excluded}(T) := \{x\in X\setminus T| Q(T+x)\}$ .
For any subset $\alpha\subset A$ , say that $T$ is $α -$ viable iff
$\forall a\in\alpha, P(a, T)$ ; and
$\forall$ finite $t\subset T, \neg Q(t)$ .

Our goal is to find a set which is $A -$ viable.

Theorm: Suppose we are given sets $A, X$ , and properties $P, Q$ as above. If $A$ can be well-ordered so that, for any $a\in A$ and any ${ < a} -$ viable subset $T\subset X$ we have $\mathsf{required}(a,T) \not\subset \mathsf{excluded}(T)$ , then there exists an $A -$ viable set.

The proof is self-evident from the framework we've set up.

Sometimes it's hard to miss

This theorem is particularly interesting in the easier-to-apply cases:

Corollary 1: If, for any $a\in A$ and any ${ < a} -$ viable subset $T\subset X$ we have $\mathsf{cardinality}(\mathsf{required}(a, T)) > \mathsf{cardinality}(\mathsf{excluded}(T))$ , then there exists an $A -$ viable set.

This conceptually simpler corollary actually covers all the examples I've seen of this general construction.

Even more interesting is that, in many cases, such surprising sets are actually quite tricky to avoid, from a certain point of view.

Corollary 2: Suppose $P$ is an atomless probability measure on $X$ . If, for any $a\in A$ and any ${ < a} -$ viable subset $T\subset X$ we have $P(\mathsf{required}(a,T)) = 1$ and $P(\mathsf{excluded}(T)) = 0$ , then a $P -$ random, $A -$ sized subset of $X$ will almost surely be $A -$ viable.

We could also relax one condition to $P(\mathsf{required}(a,T)) > 0$ , and then build up the set by adding points from the required set, but ignoring the excluded set, and we'd still end up with an $A -$ viable set almost surely.

For example, if we just pick points at random within our countable circles (iterated over by $\mathbb{Q}\times\mathbb{Q}^2$ ), there is a 100% chance that we'll avoid any pair of similar triangles.

Sets, mappings, and graphs, oh my

You can use this same framework to build other objects such as mappings or graphs by building these objects out of sets. A mapping is a set of pairs, and $Q$ can exclude any pair set which is not a mapping. A graph is a set of edges, and, again, $Q$ can exclude edges which would not make sense in a simple graph.

More Examples

There exists an infinite matrix on $[0,1] 2$ such that no finite subsquare is singular. (By the way, such a matrix is completely unsparsifiable -- you can't get a single zero more than Gaussian elimination. Please ask if you're curious about the proof.)
Given any countable sequence $d_1, d_2, d_3, \ldots$ of positive integers, there is a simple (albeit infinite) graph on vertices $1, 2, 3, \ldots$ where each node $i$ has exactly degree $d i$ .
There exists a dense point set (in any dimension above 1) without any three points on a line 1 2
Others from Gowers' post:
- There is a subset $A\subset\mathbb{Z}$ such that neither $A$ nor $\overline{A}$ contains an infinite arithmetic progression.
- There is a subset of $\mathbb{R}^2$ so that, for every positive real number there is a unique pair of points at that distance.