The pigeonhole property

The pigeonhole property is a very strong indivisibility property of a structure. We say that X has the pigeonhole property if

whenever X is the union of two disjoint substructures Y and Z, at least one of Y and Z is isomorphic to X.

That is, if we assign the points of X to two pigeonholes in any way, then one of the pigeonholes will contain a copy of X. We will let “structure” mean relational structure here, and “substructure” mean “induced substructure”: the instances of relations in Y are all instances in X for which all the arguments lie in X.

Of course, a singleton has the pigeonhole property (as, even more trivially, does the empty set); but no larger finite structure does, since it can always be divided into two strictly smaller parts. So we will look just at infinite structures. Now if our structures are just sets (with no relations), then any infinite set has the pigeonhole property (at least if we assume the Axiom of Choice); certainly any countably infinite set has the pigeonhole property, since if it is divided in two, then one at least of the two parts is also countably infinite.

From now on, only the countable case will be considered. I turn first to undirected graphs.

The countable random graph R has the pigeonhole property.

To prove this, we remember the condition which characterises R: for any two finite disjoint sets U and V of vertices, there is a vertex z joined to everything in U and to nothing in .

So let us suppose that R can be split into two pieces Y and Z, neither of which is isomorphic to R. Since Y is not isomorphic to R, we can find finite sets U1 and V1 for which no “correctly joined” witness exists in Y. Similarly there are sets U2 and V2 with no witness in Z. Now put U = U1U2 and V = V1V2. Since the whole graph is isomorphic to R, there is a witness for U and V; but, by assumption, this witness cannot lie in either Y or Z, a contradiction.

What other examples are there? Clearly the complete and null graphs have the pigoenhole property; this is just a re-statement of the pigeonhole property for a countable set. Remarkably there are no others:

The only countable graphs with the pigeonhole property are the complete and null graphs and the random graph.

The proof is just a little harder. Let X be a countable graph with the pigeonhole property. Partitioning X into the set of isolated vertices and the rest, we conclude that either X is null or it has no isolated vertices; we may assume the latter. Similarly we may assume that there is no vertex joined to all others.

Suppose that X is not isomorphic to R; let U and V be finite sets for which no correctly joined witness exists, and suppose that |UV| is miniimal subject to this. By the previous paragraph, this cardinality is at least 2. We may assume that U is non-empty; choose u in U. Then the set W of vertices joined to everything in U except u and to nothing in V is non-empty; let Y = W∪{u}, and Z the remaining points. Then Y is not isomorphic to X; for the non-existence of a witness for U and V shows that u is joined to nothing in Z, so it is an isolated vertex in Y. Also, Z is not isomorphic to X, because the sets U\{u} and V have no witness in Z (all the witnesses lie in Y).

What about directed graphs?

I will assume for a start that the directed graphs do not contain two vertices joined in both directions by edges; that is, it is an oriented graph (I will return to this point later). Now if X is an orientted graph with the pigeonhole property, then the undirected graph X* obtained by simply ignoring directions also has the pigeonhole property, and so is null, complete, or the random graph. We conclude:

An oriented graph with the pigeonhole property is null, a tournament, or an orientation of R.

(A tournament is an orientation of a complete graph; that is, any two vertices are joined by a directed edge. This describes the result of a round robin tournament where no game is drawn.)

There is nothing to be said about the null graph, but the other two cases require further consideration.

Analogously to the random graph, there is a countable random tournament, which arises with probability 1 if we choose the orientations independently at random. It shares many properties with the random graph, including a very similar number-theoretic construction: take the primes congruent to –1 (mod 4), and put an erc from p to q if q is a quadratic residue mod p. A similar argument to the one with which we began shows that the random tournament has the pigeonhole property.

But there are others. Consider the natural numbers, with arcs directed from smaller to larger; if we split it into two parts, then the infinite part is isomorphic to the whole structure. More generally, any countable totally ordered set whose order type is a limit ordinal (one with no greatest element) has the pigeonhole property. The same, of course, is true if we reverse the arcs to go from larger to smaller.

Anthony Bonato, Dejan Delić and I showed that these are the only possibilities for tournaments with the pigeonhole property.

The case of orientations of R is even harder. It should by now come as no surprise that there is a unique countable random oriented graph, which is an orientation of R, and which has the pigeonhole property. Whether or not that is all was open for a few years (I spent quite a bit of time on it) until it was resolved by Reinhard Diestel, Imre Leader, Alex Scott, and Stéphan Thomassé. They constructed and characterised an acyclic orientation of R which has the pigeonhole property, and showed that this and its converse complete the list.

A further generalisation would ask for a structure with several (but only finitely many) binary relations. A moment’s thought shows that we can “normalise” such a structure (adding new relations if necessary) so that

  • all the relations are non-empty;
  • every ordered pair of distinct points satisfies exactly one of the relations;
  • each relation is either symmetric (a graph) or skew-symmetric (an oriented graph), and in the latter case its converse is also a relation in our set).

(This handles the case of a general directed graph. There are two symmetric relations, “not joined” and “joined in both directions”, and the remaining arcs and their reversals give a pair of skew-symmetric relations.

Suppose first that all the r relations are symmetric. Then, arguing as before, we can show that there is a unique structure, the “random r-edge-coloured complete graph”. In this structure, each monochromatic subgraph is isomorphic to R.

Next, observe that in a normalised set of relations, we can replace each converse pair of skew-symmetric relations by a symmetric relation without losing the pigeonhole property. When this is done, we obtain the random r-edge-coloured complete graph. Moreover, the original skew-symmetric relation is then an orientation of R with the pigeonhole property, so we know the possibilities for its structure.

What remains is to put these pieces together. This is surely not too hard!

To finish, here briefly are some further variants.

What about asking for structures which, when the points are distributed among three pigeonholes, one contains a copy of the original? It is not hard to see that this is exactly equivalent to the original form of the pigeonhole property: if X has the p.p. and is divided into three, then either the first pigeonhole has a copy of X, or the union of the other two does; in the latter case, one further application of the property gives the result. In the other direction, simply leave the third pigeonhole empty.

Bonato, Delić, Thomassé and I considered a variant which turns out to be quite different. Suppose that, whenever the points are distributed among three pigeonholes, two of them together contain a copy of the original structure. I won’t discuss this further; see the paper for details.

What about ternary relations? This is quite a different problem, much harder. Nothing is known (to me).

A weaker version of the pigeonhole property asks only that, if the points of X are distributed in two pigeonholes, then the structure in one of the pigeonholes contains a copy of X as an indiced substructure. Such an X is called indivisible; this property has been studied by El-Zahar and Sauer, and others. There are too many of them for neat classifications.



About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition. Bookmark the permalink.

One Response to The pigeonhole property

  1. Pingback: Tweets that mention The pigeonhole property « Peter Cameron's Blog --

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s