Partitions and orientations of the Rado graph

Reinhard Diestel  Imre Leader  Alex Scott

Stéphan Thomassé

Abstract

We classify the countably infinite oriented graphs which, for every partition of their vertex set into two parts, induce an isomorphic copy of themselves on at least one of the parts. These graphs are the edgeless graph, the random tournament, the transitive tournaments of order type ω^{α}, and two orientations of the Rado graph: the random oriented graph, and a newly found random acyclic oriented graph.

1 Introduction

Which countably infinite oriented graphs G have the property that, for every partition of the vertex set of G into two parts, G is isomorphic to one of the two induced subgraphs? There are some natural examples: the edgeless graph, the random tournament, the transitive tournaments of order type ω^{α} (and their inverses), and the random oriented graph. In this paper we find another such graph, a certain random acyclic oriented graph. We show that, together with its inverse,^{1} this graph completes the list of all oriented graphs with the above property.

Let us say that a countable graph G, directed or undirected, has property P if, for every bipartition (V_{1}, V_{2}) of it vertex set, at least one of the induced subgraphs G[V_{1}] and G[V_{2}] is isomorphic to G. The simple undirected graphs with this property were characterized by Cameron [5]; they are the countably infinite complete graph, its complement, and the Rado graph.

Bonato, Cameron and Delić [1] then asked which oriented graphs have property P, and found all the tournaments (i.e. oriented complete graphs) that do: these are the random tournament, the transitive tournaments of order type ω^{α}, and the inverses of the latter (see also [3] for some related results). Since the undirected graph underlying an oriented graph with property P also has property P, the only remaining problem is to classify the orientations of the Rado graph that have property P. We shall do so in this paper.

Any non-standard terminology we use will be explained in Section 2. The reader might benefit from familiarity with the (undirected) Rado graph R, its random construction, and its basic properties such as the ‘back-and-forth’ argument to prove its uniqueness, but technically we do not assume any such knowledge. The only property of R that we shall use is that it is the unique countably infinite graph such that for every two disjoint finite sets of vertices, A and B say, it has a further vertex adjacent to every vertex in A but to none in B. The Rado graph was introduced by Rado [7] – see Cameron [4] for details and further background information.

1 The inverse of an oriented graph is obtained by reversing all its edges.

2 Terminology, basic facts, and main result

Let X be an infinite set and Y a countable set of infinite subsets of X. A partition (A, B) of X will be called a Bernstein partition with respect to Y if for every Y ∈ Y both Y ∩ A and Y ∩ B are infinite. Such partitions are easily constructed inductively. For example, let Y_{1}, Y_{2}, … be an ω-sequence of sets in Y containing each of them infinitely often. Now build the partition (A, B) in ω steps, choosing at step n two elements of Y_{n} that are not yet in A or B and assigning one to A and the other to B (and at the end assign any unassigned points of X to A, say).

An oriented graph is a directed graph G whose underlying undirected graph is simple, ie. has neither loops nor parallel edges. The inverse of G is the oriented graph obtained from G by reversing the directions of all its edges. Given vertices u, v ∈ G, we write u → v for the edge from u to v, or for the fact that G contains this edge. When α is an ordinal, the oriented graph with vertex set α = {β | β < α} and edge set {β → γ | β < γ < α} will be called the α-tournament.

We write v_{G}^{−} := {u | u → v} for the in-neighbourhood of a vertex v in G, and abbreviate v_{G}^{−} to v^{−} if no confusion can occur. A source is a vertex with empty in-neighbourhood. Similarly, v^{+} denotes the out-neighbourhood of v, and a vertex with empty out-neighbourhood is a sink. An in-section of G is any set I ⊆ V (G) such that x ∈ I and y → x imply y ∈ I. The intersection of all insections containing a given set X is the in-section generated by X. Out-sections are defined correspondingly.

An oriented graph G is well-founded if it contains no directed cycle and no infinite ‘inverse ray’, ie. no infinite path of the form … v_{−2} → v_{−1} → v_{0}. We then denote by L_{0} its set of sources and, inductively, by L_{α} the set of sources of G − ⋃_{β<α} L_{β}. The L_{α} are the levels of G, and the vertices in L_{α} are those of rank α. The smallest ordinal α such that L_{α} = ∅ is the rank of G. Observe that if G has property P, then its rank must be a limit ordinal: otherwise we partition V into the vertices of highest rank versus all the others, and note that neither part is isomorphic to G. Similarly, if G has property P and the ranks of the vertices in X ⊆ V are not cofinal in the rank of G, then G must be isomorphic to G − X.

A subgraph H of a well-founded oriented graph G is rank-preserving if its vertices have the same rank in H as in G. Note that disjoint rank-preserving subgraphs H_{1}, H_{2} can always be extended to rank-preserving subgraphs G_{1} ⊇ H_{1} and G_{2} ⊇ H_{2} that partition the vertex set of G: if we assign any remaining vertices of G to the two sides inductively, level by level, we can obviously make them keep their rank. Vertex partitions of G into two rank-preserving induced subgraphs will be called rank-preserving partitions.

We shall consider two orientations of the Rado graph. The first of these, the random oriented graph or RO, is the unique countably infinite oriented graph such that for every triple of disjoint finite subsets of vertices A, B, C there exists a vertex x such that A ⊆ x^{+}, B ⊆ x^{−} and C ∩ (x^{−} ∪ x^{+} ∪ {x}) = ∅. It is straightforward to construct such a graph inductively, and by the usual backand-forth argument it is clear that any two countable oriented graphs with this property are isomorphic. It is also clear that this oriented graph has the Rado graph as its underlying graph. We leave as an exercise the fact that RO has property P. (The proof is analogous to that of Lemma 2.2.)

For our second orientation of the Rado graph, we shall prove that there is a unique well-founded oriented graph such that every vertex has finite in-degree and for every finite set F of vertices there are infinitely many vertices v such that v^{−} = F. We shall call this the acyclic random oriented graph (see below for why), or ARO for short. It is again straightforward to construct such a graph inductively, and to prove that its underlying undirected graph has the defining property of the Rado graph. It thus remains to show uniqueness, and to check that the ARO has property P.

Lemma 2.1 The ARO is unique.

Proof. Let G_{1} and G_{2} be two countable oriented graphs that have the defining property of the ARO. Suppose we have already defined an isomorphism f from a finite in-section F_{1} of G_{1} into a finite in-section F_{2} of G_{2}. Let v be any vertex of G_{1} − F_{1}. If we can extend f to a partial isomorphism g whose domain contains F_{1} ∪ {v}, we will be able likewise to construct an isomorphism between G_{1} and G_{2} inductively, using the standard back-and-forth method. By König’s infinity lemma and our assumption that G_{1} is well-founded (with every vertex having finite in-degree), the in-section F that v generates in G_{1} is finite. Thus, F_{1} ∪ F is another finite in-section of G_{1}. To obtain g, we use the defining property of ARO for G_{2} to extend f to F_{1} ∪F level by level (of F \F_{1}), starting with the lowest level. The image of g will then be another finite in-section of G_{2}. □

Interestingly, there is also a random construction for the ARO. Take ω as the vertex set, let all edges i → j be oriented forward (ie. so that i < j), and form an oriented graph by taking these edges i → j independently with probability 2^{−(i+1)}. By construction, any oriented graph obtained in this way is well-founded, and all in-degrees are finite. Moreover, the graph obtained almost surely has the defining property of the ARO. (The proof of this mimics the standard proof that the undirected random graph is almost surely the Rado graph – see [7] or [4]. There is nothing mysterious about our edge probabilies p_{i} = 2^{−(i+1)}; the proof works for any p_{i} such that Π_{i=0}^{∞}(1 − p_{i}) > 0.)

Lemma 2.2 The ARO has property P.

Proof. Let G be a copy of the ARO, and let (G′, G′′) be a vertex partition of G into two induced subgraphs. If neither G′ nor G′′ is the ARO, then G′ has a finite set F′ of vertices such that {v ∈ G′ | v_{G′}^{−} = F′} is finite, and G′′ has a finite set F′′ of vertices such that {v ∈ G′′ | v_{G′′}^{−} = F′′} is finite. But then only finitely many vertices v of G satisfy v^{−} = F′ ∪ F′′, contradicting our assumption that G is the ARO. □

We can now state our main result.

Theorem 2.3 The only orientations of the Rado graph with property P are RO, ARO, and the inverse of ARO.

As pointed out in the Introduction, Theorem 2.3 completes the classification of the countable oriented graphs with property P.

Corollary 2.4 The countable oriented graphs with property P are precisely the following:

• the edgeless graph;

• the random tournament;

• the transitive tournaments of order type ω^{α} and their inverses;

• the random oriented graph RO;

• the random acyclic oriented graph ARO and its inverse. □

We shall prove Theorem 2.3 in the next three sections. From now on, we consider a fixed orientation G = (V, E) of the Rado graph that has property P. Our proof proceeds by a series of lemmas, gradually learning more and more about the structure of G.

3 Finite in-degrees

Lemma 3.1 If G ≠ RO then either G or its inverse is well-founded.

Proof. We assume that G ≠ RO. Let us begin by showing that G has a source or a sink. As G ≠ RO, there are three disjoint finite sets A, B, C ⊂ V such that no vertex x ∈ G satisfies A ⊆ x^{+}, B ⊆ x^{−} and C ∩ (x^{+} ∪ x^{−} ∪ {x}) = ∅. Let us choose A, B, C with |A ∪ B ∪ C| minimum. Since G is an orientation of the Rado graph, A ∪ B is non-empty. We assume that A ≠ ∅; the case of B ≠ ∅ is analogous with reverse edges. Pick a ∈ A, let G_{1} be the subgraph of G induced by (A ∪ B ∪ C ∪ a^{−}) \ {a}, and let G_{2} be the subgraph induced by the complement of this set. Apply P to the partition (G_{1}, G_{2}). If G ≃ G_{1}, then by the minimality of |A ∪ B ∪ C| there is a vertex x ∈ G_{1} such that A \ {a} ⊆ x^{+}, B ⊆ x^{−} and C ∩ (x^{−} ∪ x^{+} ∪ {x}) = ∅. But then x ∈ a^{−} and hence even A ⊆ x^{+}, so this contradicts the choice of A, B, C. Therefore G ≃ G_{2}. Since a is a source of G_{2}, we have thus proved that G has a source (or a sink).

By reversing all edges if necessary, we may thus assume that G has a source. Let S be a maximal well-founded in-section of G. Apply property P to the partition (S, V \ S). As S is maximal, G cannot be isomorphic to G − S: then G − S would contain a source s, and S ∪ {s} would be larger a well-founded in-section. So G is isomorphic to G[S] and therefore well-founded. □

From now on we assume that G is well-founded, and show that G = ARO. Recall that the levels of G are denoted by L_{0}, L_{1}, . . ..

Lemma 3.2 G has infinitely many sources.

Proof. Suppose not, ie. suppose that L_{0} is finite. Pick x ∈ L_{0}, and consider the partition (X, V \ X), where X is the out-section generated by x. Clearly G ≄ G − X, since G − X has the smaller set L_{0} \ {x} as its set of sources. Therefore G ≃ G[X], so G has a single source. Since G is an orientation of the Rado graph, it has two non-adjacent vertices u, v. But then G−(u^{−} ∪v^{−}) has at least two sources and is isomorphic to G by property P, a contradiction. □

Lemma 3.3 If every vertex of G has finite in-degree, then G = ARO.

We shall spend most of the remainder of this section proving Lemma 3.3. Asssume that every vertex of G has finite in-degree. Then G has rank at most ω, and since G satisfies P its rank is exactly ω. Given a set U ⊆ V, let us write U^{+} := U ∪ {u^{+} | u ∈ U}.

Claim 3.4 Whenever F ⊂ V is finite and x ∈ V \ F, we have x^{+} ⊈ F^{+}.

Proof. Suppose not, and let (F, x) be a counterexample with |F | minimum. Observe that F ≠ ∅, since otherwise x is a sink and hence has only finitely many neighbours, which is impossible in the Rado graph. Pick y ∈ F, and consider the partition (X, V \ X), where X = (y^{+} \ ({x} ∪ F)) ∪ {y}. Since y is adjacent to every other vertex in X but the Rado graph has no vertex adjacent to every other vertex, G ≄ G[X]. Therefore G ≃ G − X. But then the fact that x_{G−X}^{+} ⊆ (F \ {y})_{G−X}^{+} contradicts the minimality of F. □

Claim 3.5 For every x ∈ V there is a y ∈ V such that y^{−} = {x}.

Proof. We inductively construct a partition of V into sets V_{1} and V_{2} that have the desired property in the subgraphs they induce, ie., are such that for every x ∈ V_{i} there is a y ∈ V_{i} with y_{G[V_{i}]}^{−} = {x} (i = 1, 2). Then, by P, also G will have this property.

Let (x_{i})_{i∈ω} be an enumeration of V such that i < j for every edge x_{i} → x_{j} of G. (Such an enumeration exists, because G is well-founded.) Suppose we have already defined two disjoint finite sets X_{n}, Y_{n} ⊂ V such that {x_{0}, …, x_{n}} ⊆ X_{n} ∪ Y_{n} and for every x_{i} ∈ X_{n} (resp. Y_{n}) with i ≤ n there exists y ∈ X_{n} (resp. Y_{n}) such that x_{i} ∈ y^{−} and y^{−} \ {x_{i}} ⊆ Y_{n}, (resp. X_{n}). Let us show that we can extend X_{n} and Y_{n} to sets X_{n+1} and Y_{n+1} with the corresponding properties for n + 1.

Adding x_{n+1} to X_{n} if necessary, we may assume that x_{n+1} ∈ X_{n} ∪Y_{n}. Since x_{n+1}^{+} ⊈ ((X_{n}∪Y_{n})\{x_{n+1}})^{+} by Claim 3.4, there exists a vertex y ∈ V \(X_{n}∪Y_{n}) such that y^{−} ∩ (X_{n} ∪ Y_{n}) = {x_{n+1}}. If x_{n+1} ∈ X_{n}, we put X_{n+1} := X_{n} ∪ {y} and Y_{n+1} := Y_{n} ∪ (y^{−} \ {x_{n+1}}). If x_{n+1} ∈ Y_{n} we swap the roles of X and Y, i.e. add y to Y_{n} and its in-neighbours to X_{n}. Then V_{1} = ⋃ X_{i} and V_{2} = ⋃ Y_{i} form the desired partition of V. □

To complete the proof of Lemma 3.3, we now prove that G = ARO. Suppose not. Then G violates the defining property of the ARO, ie. there exists a finite set F ⊂ V such that A := {v ∈ V | v^{−} = F } is finite. By Lemma 3.2, every such F is non-empty; we choose F so that |F ∪ A| is minimum.

Let S denote the out-section generated by A, and consider the partition (S, V \ S) of V. By Lemma 3.2 we have G ≄ G[S]. So G is isomorphic to the graph G − S, which contains F but no vertex v with v_{G−S}^{−} = F. By the choice of F, this implies A = ∅.

Pick x ∈ F, and consider a maximal set X ⊆ V such that

• X ∩ F = {x}

• (V \ (F ∪ x^{+})) ⊆ X

• for every v ∈ x^{+} ∩ X we have v^{−} ∩ X ≠ {x}.

By Claim 3.5 applied to x, we have G ≄ G[X]. So G ≃ G − X. But in G − X there is no vertex v with v_{G−X}^{−} = F \ {x}: any such v would lie in G − X − F ⊆ x^{+}, giving v^{−} ⊇ F and hence v^{−} = F (since v^{−} ∩ X = {x} by the maximality of X), contradicting the fact that A = ∅. This contradicts the minimality of |F ∪ A| and completes the proof of Lemma 3.3.

To complete our proof of Theorem 2.3, it suffices by Lemma 3.3 to show that G has no vertex of infinite in-degree.

Lemma 3.6 If G has a vertex of infinite in-degree, and α is the least rank of such a vertex, then α ∈ {1, ω}.

Proof. Let v be a vertex of infinite in-degree and rank α. Since all vertices of rank ω have infinite in-degree, clearly α ≤ ω. If α < ω, then for some finite i the set X = v^{−} ∩ L_{i} is infinite. If we delete all the vertices of rank < α except those in X, we obtain a graph in which v has rank 1 and infinite in-degree. Since this graph is isomorphic to G by property P, it follows that α ∈ {1, ω}. □

In the remaining two sections we shall treat these two cases α = 1 and α = ω in turn.

4 Rank 1 vertices of infinite in-degree

Our aim in this section is to dispose of the first of our two cases:

Lemma 4.1 G has no rank 1 vertex of infinite in-degree.

For our proof of Lemma 4.1, let I denote the set of rank 1 vertices of infinite in-degree. Suppose that I ≠ ∅.

Claim 4.2 The set I is infinite.

Proof. Suppose I is finite. Let X be the out-section generated by I. Then the partition (X, V \ X) of V violates P: while G[X] has only finitely many sources (cf. Lemma 3.2), the graph G−X has no rank 1 vertex of infinite in-degree. □

Let G_{I} denote the simple undirected graph with vertex set I in which uv is an edge if and only if u^{−} ∩ v^{−} is finite.

Claim 4.3 G_{I} has property P.

Proof. Let (X, Y) be any bipartition of I. Let (A, B) be a Bernstein partition of L_{0} with respect to {v^{−} : v ∈ I}∪{u^{−}∩v^{−} : u, v ∈ I and |u^{−}∩v^{−}| = ∞}. Extend (A ∪ X, B ∪ Y) to a rank-preserving partition (V_{A}, V_{B}) of V. By property P for G, we may assume that G ≃ G[V_{A}] =: G′. But the set I′ of rank 1 vertices of infinite in-degree in G′ is precisely X, so G_{I}[X] = G′_{I′} ≃ G_{I} by the choice of (A, B). □

By Cameron’s theorem [5], Claim 4.3 implies that G_{I} is either the infinite complete graph or the infinite edgeless graph or the Rado graph.

Claim 4.4 G_{I} is not the Rado graph.

Proof. If G_{I} is the Rado graph, it has two non-adjacent vertices u, v. By definition of G_{I}, these are elements of I such that u^{−} ∩ v^{−} is infinite. By P, we know that G ≃ G − (u^{−}△v^{−}). Therefore G has two vertices x, y ∈ I with x^{−} = y^{−}. Then x and y have the same neighbourhood in G_{I}. But no two vertices of the Rado graph have the same neighbourhood. □

Claim 4.5 G_{I} is not the infinite complete graph.

Proof. Let (x_{i})_{i<ω} be an enumeration of I. If G_{I} is complete, then x_{i}^{−} ∩ x_{j}^{−} is finite for all i ≠ j. We may therefore select an infinite sequence (y_{i})_{i<ω} of vertices in L_{0} such that y_{i} ∈ x_{i}^{−}\(x_{0}^{−}∪…∪x_{i−1}^{−}) for all i. Put Y := {y_{i} | i < ω}, and extend (Y ∪ I, L_{0} \ Y) to a rank-preserving partition (A, B) of V. Then neither G[A] nor G[B] has any rank 1 vertices of infinite in-degree. By our assumption that I ≠ ∅, this contradicts property P for G. □

So G_{I} is the infinite edgeless graph. In other words, the in-neighbourhoods of two vertices u, v ∈ I always meet in an infinite set. Observe that u^{−} \ v^{−} and v^{−} \ u^{−} cannot both be infinite, because any isomorphism from G \ (u^{−} ∩ v^{−}) to G (which exists by P) would then map u and v to adjacent vertices of G_{I}.

Let H_{I} denote the simple undirected graph on I in which uv is an edge if and only if u^{−}△v^{−} is infinite.

Claim 4.6 H_{I} has property P.

Proof. Let (X, Y) be any bipartition of I. Let (A, B) be a Bernstein partition of L_{0} with respect to {v^{−} : v ∈ I} ∪ {u^{−}△v^{−} : u, v ∈ I and |u^{−}△v^{−}| = ∞}. Extend (A ∪ X, B ∪ Y) to a rank-preserving partition (V_{A}, V_{B}) of V. By property P for G, we may assume that G ≃ G[V_{A}] =: G′. Define I′ and H′_{I′} for G′ in analogy to I and H_{I} in G, and note that I′ = X. Hence H_{I}[X] = H′_{I′} ≃ H_{I} by the choice of (A, B). □

As before, H_{I} is isomorphic to the Rado graph, the infinite complete graph, or the infinite edgeless graph. The first two possibilities are ruled out by the fact that for every two vertices u, v ∈ I the graph G − (u^{−}△v^{−}) is isomorphic to G but has two rank 1 vertices of infinite in-degree which, in the counterpart of H_{I}, are non-adjacent and have the same neighbourhood. Thus, H_{I} is the infinite edgeless graph. In other words, the in-neighbourhoods in G of the vertices in I differ pairwise only by finite sets.

Claim 4.7 Every vertex in L_{0} has an out-neighbour in I.

Proof. Denote by Y the set of vertices in L_{0} with no out-neighbour in I. Extend (Y, (L_{0} \ Y) ∪ I) to a rank-preserving partition (A, B) of V. Since G[A] has no rank 1 vertex of infinite in-degree, G is isomorphic to G[B]. The claim follows. □

To conclude the proof of Lemma 4.1, let us derive a final contradiction. Pick u ∈ I, and extend (u^{−}, L_{0} \ u^{−}) to a rank-preserving partition (A, B) of V. If G ≃ G[B], then G[B] has a rank 1 vertex v of infinite in-degree. Then v ∈ I, and v^{−} \ u^{−} is infinite. But then uv is an edge of H_{I}, a contradiction. Hence G ≃ G[A], by property P. As u must be in A, we deduce that G has a rank 1 vertex v with v^{−} = L_{0}.

Next, we show that G has a rank 1 vertex with only one in-neighbour. Pick a vertex u ∈ L_{0} that sends an edge to a vertex v ∈ L_{1}. By property P, G is isomorphic to the graph obtained from G by deleting all vertices in L_{0} except u. In this graph, v still has rank 1 but has no in-neighbour other than u.

Let C be the set of all vertices of G with infinitely many in-neighbours in L_{0}. Let (A, B) be a Bernstein partition of L_{0} with respect to {v^{−} ∩ L_{0} | v ∈ C}. Now G ≄ G[A ∪ C], because G[A ∪ C] has no rank 1 vertex with only one in-neighbour. By property P, therefore, G is isomorphic to G − A − C. But, unlike G, this graph has no vertex v whose in-neighbourhood is the entire set of sources. (Since that set includes B, this would put v in C.)

This completes the proof of Lemma 4.1.

5 Rank ω vertices of infinite in-degree

Let F := ⋃_{i<ω} L_{i} denote the set of vertices of finite rank in G. Recall that, by Lemmas 3.6 and 4.1, every vertex in F has finite in-degree.

By Lemma 3.3, our proof of Theorem 2.3 will be complete once we have shown the following:

Lemma 5.1 L_{ω} = ∅.

This entire section is devoted to the proof of Lemma 5.1. Suppose L_{ω} ≠ ∅. Then L_{ω} must be infinite: otherwise, deleting F would leave an isomorphic copy of G with only finitely many sources, which would contradict Lemma 3.2.

Claim 5.2 Let v ∈ V be any vertex of infinite in-degree. Then every infinite subset X of v^{−} contains an ω-tournament.

Proof. If X contains an infinite independent set A (i.e., a set inducing no edge), we consider the graph G′ obtained from G by deleting the in-section generated by v, except A and v itself. By property P, this graph G′ is isomorphic to G. But in G′, v is a rank 1 vertex of infinite in-degree, contradicting Lemma 4.1. Hence by Ramsey’s theorem, X contains an ω-tournament or its inverse. The latter case is impossible, because G is well-founded. □

Corollary 5.3 For every v ∈ V and every α, the set v^{−} ∩ L_{α} is finite. □

Corollary 5.4 If an induced subgraph H of G contains a vertex v and infinitely many vertices from v^{−}, then v has infinite rank in H. In particular, if V (H)∩F is one side of a Bernstein partition of F with respect to {v^{−} | v ∈ L_{ω}}, then the vertices of L_{ω} will have rank ω also in H. □

Claim 5.5 There exists a vertex u ∈ L_{ω} such that the in-section generated by u^{−} in G does not exceed u^{−}.

Proof. Pick v ∈ L_{ω}, and let G′ be obtained from G by deleting F \ v^{−}. By Claim 5.4, v still has rank ω in G′. As vertices of infinite rank in G may drop to finite rank in G′, the set F′ of vertices of finite rank in G′ may be a proper superset of v^{−}. However, no vertex of F′ \ v^{−} lies below v^{−} (i.e. in the in-section generated by v^{−}) in G′. So the in-section generated by v^{−} in G′ is exactly v^{−} = v_{G′}^{−}. Now the claim follows as G′ ≃ G by property P. □

More generally, we have the following for all vertices in L_{ω}:

Claim 5.6 For every v ∈ L_{ω}, the in-section generated by v in G exceeds v^{−} only by a finite set.

Proof. Let U denote the set of all v ∈ L_{ω} such that the in-section F_{v} generated by v exceeds v^{−} by an infinite set. In every such set F_{v} we can inductively find an infinite set E_{v} = {x_{i} → y_{i} | i < ω} of independent edges such that y_{i} ∈ v^{−} and x_{i} ∉ v^{−}. (Indeed, by König’s infinity lemma our assumption that all vertices in F have finite in-degree implies that the in-section S generated by {y_{1}, …, y_{n}} is finite; we can therefore find x_{n+1} → y_{n+1} in F_{v} \ S.)

As in the standard construction of Bernstein partitions, we can construct a partition (A, B) of F such that for every v ∈ L_{ω} both A and B meet v^{−} in an infinite set, and for every v ∈ U both A and B contain infinitely many edges from E_{v}. By Corollary 5.4, the vertices of infinite rank in G also have infinite rank in both G−A and G−B. We can therefore extend (A∪U, B ∪(L_{ω} \U)) to a partition (X, Y) of V that preserves the rank of all vertices that have infinite rank in G. Now G ≄ G[X] by Claim 5.5, since in G[X] every vertex v of rank ω generates an in-section that exceeds v_{G[X]}^{−} by an infinite set. So G is isomorphic to G[Y], where the in-section generated by any vertex v of rank ω exceeds v_{G[Y]}^{−} only finitely. □

Let G_{ω} denote the simple undirected graph on L_{ω} in which uv is an edge if and only if u^{−} ∩ v^{−} is finite.

Claim 5.7 G_{ω} has property P.

Proof. Let (X, Y) be any bipartition of L_{ω}. Let (A, B) be a Bernstein partition of F with respect to {v^{−} : v ∈ L_{ω}} ∪ {u^{−} ∩ v^{−} : u, v ∈ L_{ω} and |u^{−} ∩ v^{−}| = ∞}. By Corollary 5.4, X and Y are exactly the sets of rank ω vertices in G[A∪X] and G[B ∪ Y], respectively. Extend (A ∪ X, B ∪ Y) to a partition (V_{A}, V_{B}) of V that preserves the ranks of all vertices of infinite rank. By P for G, we may assume that G ≃ G[V_{A}]. By the choice of (A, B), this implies G_{ω} ≃ G[V_{A}]_{ω} = G_{ω}[X], where G[V_{A}]_{ω} is defined for G[V_{A}] as G_{ω} is defined for G. □

Claim 5.8 G_{ω} is the infinite complete graph.

Proof. From Claim 5.7 and [5] we know that G_{ω} is either the Rado graph R, or the infinite complete graph, or the infinite edgeless graph.

If G_{ω} ≃ R, then G_{ω} has two non-adjacent vertices u, v ∈ L_{ω}. Deleting F \ (u^{−} ∩ v^{−}) from G yields a graph G′ ≃ G such that u_{G′}^{−} = u^{−} ∩ v^{−} = v_{G′}^{−}. By Corollary 5.4 this implies that u and v have rank ω also in G′ (since u^{−} ∩ v^{−} is infinite by the choice of u and v), and in the graph G′_{ω} defined for G′ in analogy to G_{ω} for G, the vertices u, v have the same neighbourhood. But this cannot happen in the Rado graph.

Suppose now that G_{ω} is the infinite edgeless graph. Pick v ∈ L_{ω}, and let G′ := G − (F \ v^{−}). Then G′ ≃ G. As |u^{−} ∩ v^{−}| = ∞ for every u ∈ L_{ω}, every u ∈ L_{ω} still has rank ω in G′, and hence every vertex of infinite rank in G still has infinite rank in G′. In other words, the vertices of finite rank in G′ are only those in v^{−}. In particular, all the sources of G′ (which form an infinite independent set by Lemma 3.2) send an edge to v, contradicting Corollary 5.3. □

Let J := {v ∈ V : |v^{−} ∩ F | = ∞}. Since the vertices in F have finite indegrees, we have J ∩ F = ∅. Let G_{J} be the graph on J in which u, v ∈ J are adjacent if and only if u^{−} ∩ v^{−} ∩ F is infinite.

By Claim 5.8, L_{ω} is an independent set of vertices in G_{J}. More generally, we have the following:

Claim 5.9 Adjacent vertices of G_{J} are also adjacent in G.

Proof. Suppose u, v ∈ J are adjacent in G_{J} but not in G. Let G′ be obtained from G by deleting (u^{−} ∪v^{−})\F. Then u, v ∈ G′, and both vertices have rank ω in G′. As G′ ≃ G by property P and u_{G′}^{−} ∩ v_{G′}^{−} = u^{−} ∩ v^{−} ∩ F is infinite, this contradicts Claim 5.8. □

Claim 5.10 For every v ∈ J, there is an ω-tournament K(v) ⊆ G[v^{−} ∩ F] that contains all but finitely many vertices of the in-section generated by v^{−}∩F in G.

Proof. We first prove the claim for all v ∈ L_{ω} =: {v_{1}, v_{2}, …}. By Claim 5.2, every v_{i}^{−} has a subset K_{i} that induces an ω-tournament in G. Put D_{i} := v_{i}^{−}\K_{i}. Let G′ be the graph obtained from G by deleting, inductively for all i < ω, the sets D_{i} \ (v_{1}^{−} ∪ … ∪ v_{i−1}^{−}). By Claim 5.8, each of the ω-tournaments K(v_{i}) := K_{i} \ (D_{1} ∪ … ∪ D_{i−1}) is infinite and differs from the in-neighbourhood of v_{i} in G′ only by a subset of D_{i} ∩ (v_{1} ∪ … ∪ v_{i−1}^{−}), which is finite. By Claim 5.6, then, K(v_{i}) differs only finitely from the entire in-section generated by v_{i} in G′. As G′ ≃ G by property P, and every v ∈ L_{ω} has rank ω also in G′, this proves the claim for all v ∈ L_{ω}.

To reduce the case of arbitrary v ∈ J to the special case above, delete v^{−} \F to obtain a subgraph G′ ⊆ G in which v has rank ω and v_{G′}^{−} = v^{−} ∩ F. This set generates identical in-sections in G′ and in G: although G′ can have vertices of finite rank that are not in F, no such vertices can lie below v^{−} ∩ F in G′. As G′ ≃ G by property P, the in-section generated by v_{G′}^{−} in G′ differs only finitely from an ω-tournament K_{G′}(v) ⊆ G′[v_{G′}^{−}] = G[v^{−} ∩ F]. □

Claim 5.11 Whenever u, v ∈ J are adjacent in G_{J}, the sets u^{−} ∩F and v^{−} ∩F differ only finitely.

Proof. Let X := u^{−} ∩ v^{−} ∩ F; as u, v are adjacent in G_{J}, this is an infinite set. By Claim 5.10, all but finitely many of these vertices lie in K(u); in particular, X ∩ V (K(u)) is infinite. As K(u) is an ω-tournament, this implies that the insection Y generated by X includes V (K(u)). But Y is a subset of the in-section generated by u^{−} ∩ F, which by Claim 5.10 exceeds V (K(u)) only finitely. So Y includes V (K(u)) but exceeds it only finitely. Now the same is true for the set u^{−} ∩ F (again by Claim 5.10), so this set differs from Y only finitely.

In the same way, Y differs only finitely from v^{−} ∩ F. Hence u^{−} ∩ F and v^{−} ∩ F differ only finitely, as claimed. □

Claim 5.12 The components of G_{J} are complete subgraphs of G_{J}. Their vertex sets induce (well-ordered) tournaments in G.

Proof. By Claim 5.11, adjacency in G_{J} is transitive. This implies the first assertion. The second follows from Claim 5.9, because G is well-founded. □

Claim 5.13 G_{J} has an isolated vertex.

Proof. Pick v ∈ L_{ω}, and let C be the subgraph of G induced by the component of G_{J} containing v. By Claim 5.12, C is a (well-ordered) tournament. Hence G ≄ C − v, so G is isomorphic to G − (C − v). And in this graph, v is a vertex of rank ω that is isolated in the counterpart to G_{J} (ie., v shares only finitely many in-neighbours of finite rank with any other vertex). □

Claim 5.14 G_{J} has no edge.

Proof. Let (A, B) be a Bernstein partition of F with respect to {v^{−} | v ∈ J}. By Claim 5.11, this partition also splits any infinite set of the form u^{−} ∩ v^{−} ∩ F with u, v ∈ J into two infinite sets. Extend this partition by adding every isolated vertex of G_{J} to A and the rest of J to B. Then extend this partition inductively, level by level, so that every new vertex again has infinite rank in the graph induced by its side. Let this partition of V be denoted by (V_{A}, V_{B}).

By construction of (V_{A}, V_{B}), the vertices of finite rank in G[V_{A}] are only those in A. Hence the vertices of G[V_{A}] that have infinitely many in-neighbours of finite rank are precisely those in J ∩V_{A} =: J_{A}. Let G[V_{A}]_{J_{A}} be the undirected graph on J_{A} defined in analogy to G_{J}; then two vertices from J_{A} are adjacent in G[V_{A}]_{J_{A}} if and only if they are adjacent in G_{J}. The same remarks apply, with the analogous definitions, to G[V_{B}]_{J_{B}}.

Now G ≄ G[V_{B}] by Claim 5.13, because G[V_{B}]_{J_{B}} has no isolated vertex. So G ≃ G[V_{A}], and hence G_{J} ≃ G[V_{A}]_{J_{A}}. But in G[V_{A}]_{J_{A}} every vertex is isolated.

□

Claim 5.15 If u and v are distinct vertices of G, then u^{−} ∩ v^{−} is finite.

Proof. Suppose |u^{−} ∩ v^{−}| = ∞. By Claim 5.2, u^{−} ∩ v^{−} has a subset X that spans an ω-tournament in G. Assume that u has rank at most the rank of v, and let G′ be obtained from G by deleting all vertices of smaller rank except those in X. Then u_{G′}^{−} = X, so u has rank ω in G′. Moreover, G′ ≃ G by property P. Let J′ and G′_{J′} be defined for G′ as J and G_{J} are defined for G. Then u and v are adjacent vertices of G′_{J′} ≃ G_{J}, contradicting Claim 5.14. □

To complete the proof of Lemma 5.1, let us now show that every vertex in G has finite in-degree. Let x_{1}, x_{2}, … be an enumeration of V. For each i, put X_{i} := x_{i}^{−}∪{x_{i}}. Define a partition (A, B) of V in ω steps, as follows. Let A_{i} and B_{i} denote the sets of vertices that have been assigned to A respectively B until (and including) step i. These sets will be chosen so that A_{i} ∪B_{i} = X_{1} ∪…∪X_{i}.

At step i+1, check whether x_{i+1} ∈ A_{i}∪B_{i}; if not, assign x_{i+1} arbitrarily to A or B. Now assume that x_{i+1} has already been assigned to A. (Otherwise, swap the roles of A and B in what follows.) By A_{i} ⊆ X_{1} ∪ … ∪ X_{i} and Claim 5.15, the set X_{i+1} ∩ A_{i} is finite. We now define A_{i+1} and B_{i+1} by keeping A as it is (ie., putting A_{i+1} := A_{i} ∪ {x_{i+1}}) and letting B_{i+1} := B_{i} ∪ (x_{i+1}^{−} \ A_{i}). Then again A_{i+1} ∪ B_{i+1} = X_{1} ∪ … ∪ X_{i+1}, as required for the induction.

By construction of (A, B), every x_{i} has only finitely many in-neighbours in its own partition set. Since G is isomorphic to G[A] or to G[B] by property P, every vertex of G has finite in-degree.

This completes the proof of Lemma 5.1, and of Theorem 2.3. □

Let us close by mentioning that we do not know whether or not the Rado graph R is ‘edge-invisible’, in the sense that whenever we partition the edges of R into two classes then the subgraph formed by one of the classes contains a copy of R as an induced subgraph. If we insist that the copy of R should be induced in the whole of R (rather than just in its class) then this is known to be false: Erdős, Hajnal and Pósa [6] constructed a partition of the edges of R into two classes such that every induced copy of R contains edges from both classes.

References

[1] A. Bonato, P.J. Cameron and D. Delić, Tournaments and orders with the pigeonhole property, Canad. Math. Bull. 43 (2000), 397-405.

[2] A. Bonato, P.J. Cameron, D. Delić and S. Thomassé, Generalized pigeonhole properties of graphs and oriented graphs, European J. Combin. 23 (2002), 257-274.

[3] A. Bonato and D. Delić, A note on orientations of the infinite random graphs, manuscript (2003).

[4] P.J. Cameron, Aspects of the random graph, Graph Theory and Combinatorics (Cambridge, 1983), 65-79.

[5] P.J. Cameron, Oligomorphic Permutation Groups, Cambridge University Press, Cambridge, 1990.

[6] P. Erdős, A. Hajnal and L. Pósa, Strong embeddings of graphs into colored graphs, in Infinite and Finite Sets (Colloq., Keszthely, 1973), Colloq. Math. Soc. Janos Bolyai 10 (1975), pp. 585-595.

[7] R. Rado, Universal graphs and universal functions, Acta Arith. 9 (1964), 331-340.

Reinhard Diestel Mathematisches Seminar Universität Hamburg Bundesstraße 55 D – 20146 Hamburg

diestel@math.uni-hamburg.de

Imre Leader DPMMS/CMS University of Cambridge Wilberforce Road GB – Cambridge CB3 0WB

                          i.leader@dpmms.cam.ac.uk

Alex Scott Department of Mathematics University College London Gower Street GB – London WC1E 6BT

scott@math.ucl.ac.uk

Stéphan Thomassé Laboratoire LaPCS UFR de Mathématiques Université Claude Bernard Lyon 1 50, avenue Tony Garnier, Domaine de Gerland Bâtiment RECHERCHE [B] F – 69367 Lyon Cedex 07

                          thomasse@univ-lyon1.fr

Version 30.05.2005