0  bipart  14.7.νmber

INFINITE HOMOGENEOUS

BIPARTITE GRAPHS

WITH UNEQUAL SIDES

February 1992

Martin Goldstern

2. Mathematisches Institut FU Berlin, Arnimallee 3 1000 Berlin 33, Germany

               goldstrn@math.fu-berlin.de

Rami Grossberg

Department of Mathematics, Carnegie Mellon University Pittsburgh, PA 15213, USA

                      Rami@cmu.edu

Menachem Kojman

Institute of Mathematics Hebrew University of Jerusalem, Givat Ram 91904 Jerusalem, Israel

                   kojman@CS.bgu.ac.il

ABSTRACT. We call a bipartite graph homogeneous if every finite partial automorphism which respects left and right can be extended to a total automorphism.

A (κ, λ) bipartite graph is a bipartite graph with left side of size κ and right side of size λ. We show that there is a homogeneous (ℵ_{0}, 2^{ℵ_{0}}) bipartite graph of girth 4 (thus answering negatively a question by Kupitz and Perles), and that depending on the underlying set theory all homogeneous (ℵ_{0}, ℵ_{1}) bipartite graphs may be isomorphic, or there may be 2^{ℵ_{1}} many isomorphism types of (ℵ_{0}, ℵ_{1}) homogeneous graphs.

Goldstern, Grossberg, Kojman: Bipartite Graphs

§0. Introduction

A homogeneous graph is one in which every finite partial automorphism extends to a total automorphism. All countable homogeneous graphs were classified in [LW], and countable tournaments were classified in [L] (see also [C]). When looking at countable homogeneous bipartite graphs, one sees that there are only five types of such graphs: complete bipartite graphs, empty bipartite graphs, perfect matchings, complements of perfect matchings and the countable random bipartite graph.

In this paper we study the structure of uncountable homogeneous bipartite graphs which have two sides of unequal cardinalities. We must make the following demand on the notion of automorphism to admit this class of graphs: a bipartite graph has a left and a right side, and automorphisms preserve sides (this is necessary, as otherwise a partial finite automorphisms which switches two vertices from the different sides cannot be extended to a total automorphism).

We call a bipartite homogeneous graph with a left side of cardinality κ and a right side of cardinality λ > κ and which is neither complete nor empty, a (κ, λ) saS graph. The name should mean “symmetric asymmetric”, where the symmetry is local, and the asymmetry is global, in having a bigger right hand side. (The demand that saS graphs are neither complete nor empty is to avoid trivial cases).

The paper is organized as follows: In Section 1 we classify homogeneous bipartite graphs, and remark that there are only five types of countable homogeneous bipartite graphs. Then we prove the existence of (ℵ_{0}, 2^{ℵ_{0}}) saS graphs. The existence of such graphs answers negatively the following question by J. Kupitz and M. A. Perles: is it true that in every connected locally 3-symmetric (see below) bipartite graph of girth 4 which is not a complete bipartite graphs both sides are of equal cardinality? (Kupitz and Perles proved that the answer is “yes” if the graph is finite).

In the second section we count the number of non isomorphic (ℵ_{0}, ℵ_{1}) saS graphs under the assumption of the weak continuum hypothesis. We prove that the weak continuum hypothesis (i.e., 2^{ℵ_{0}} < 2^{ℵ_{1}}, which is a consequence of the continuum hypothesis) implies that there are 2^{ℵ_{1}} pairwise non isomorphic (ℵ_{0}, ℵ_{1}) saS graphs.

In the third section we show that ¬CH + MA implies that there is only one (ℵ_{0}, ℵ_{1}) saS graph up to isomorphism. These results together show that the number of isomorphism types of (ℵ_{0}, ℵ_{1}) saS graphs is independent of ZFC, the usual axioms of Set Theory.

Our interest in homogeneous bipartite graphs started when M. Perles introduced to us the question of the existence of a locally symmetric infinite bipartite graphs of girth 4 with sides of unequal cardinalities. (See 1.5 below.) We are grateful to him for this, and not less for his careful reading of the paper and his helpful suggestions.

The notation we use is mostly standard, but we nevertheless specify it here.

0.1 NOTATION:

(1) A bipartite graph is a triple Γ = ⟨L, R, E⟩ = ⟨L^{Γ}, R^{Γ}, E^{Γ}⟩ such that L ∩ R = ∅, L and R are non-empty and E ⊆ {{x, y} : x ∈ L, y ∈ R}. L ∪ R is the set of vertices of Γ, E is the set of edges. Members of L and R are called left and right vertices, respectively. Abusing notation, we sometimes write v ∈ Γ, instead of v ∈ L ∪ R. Abusing notation even more, we may write L×R for {{x, y} : x ∈ L, y ∈ R}. Γ = ⟨L, R, E⟩ is a subgraph of Γ′ = ⟨L′, R′, E′⟩ if L ⊆ L′, R ⊆ R′, E ⊆ E′. It is called an induced subgraph if in addition E = E′ ∩ L × R.

(2) A bipartite graph Γ = ⟨L, R, E⟩ is complete if for all x ∈ L, y ∈ R we have {x, y} ∈ E and is called empty if E = ∅. If Γ = ⟨L, R, E⟩, the complement graph of Γ, is the graph whose edge set is L × R \ E

(3) If Γ is a bipartite graph and v ∈ Γ, the set Γ(v) = {u : u ∈ Γ, {v, u} ∈ E} is called the set of neighbors of v. Γ is called a perfect matching iff Γ(u) is a singleton for every u ∈ Γ.

(4) A square in a graph Γ is a quadruple of distinct vertices, v_{1}, ⋯, v_{4} such that {v_{1}, v_{4}} ∈ E and {v_{i}, v_{i+1}} ∈ E for 1 ≤ i ≤ 3.

(5) A partial homomorphism between two graphs Γ_{1}, Γ_{2} is a partial map f : Γ_{1} → Γ_{2} with the property that for all x, y ∈ dom(f): {x, y} ∈ E_{1} iff {f(x), f(y)} ∈ E_{2}

(6) A partial isomorphism between bipartite graphs Γ and Γ′ is a 1-1 partial map from L^{Γ} ∪ R^{Γ} into L^{Γ′} ∪ R^{Γ′} which preserves left and right (i.e., f[L^{Γ}] ⊆ L^{Γ′}, f[R^{Γ}] ⊆ R^{Γ′}) and preserves edges and non edges (i.e., {u, v} ∈ E^{Γ} iff {f(u), f(v)} ∈ E^{Γ′} for all u, v ∈ domf). Such a partial isomorphism f is called a (total) isomorphism if f is a bijection between the vertices of Γ and Γ′. f is called a (partial) automorphism of Γ if f is a (partial) isomorphism of Γ to Γ itself. (So we only consider (partial) automorphisms which respect left and right sides.) Aut(Γ) is the group of all automorphisms of Γ.

(7) A bipartite graph Γ is locally n-symmetric if there is some H ⊆ Aut(Γ) such that for every v ∈ Γ and every two n-tuples of neighbors of v, x_{1}, ⋯, x_{n} and y_{1}, ⋯, y_{n}, there is an automorphism φ ∈ H such that φ(v) = v and φ(x_{i}) = y_{i} for all 1 ≤ i ≤ n. In such a case we say that H acts on Γ in a locally n-symmetric manner.

(8) A bipartite graph Γ is homogeneous if every finite partial automorphism can be extended to an automorphism. If H ⊆ Aut(Γ) has the property that for every finite partial automorphism f of Γ there is an automorphism in H which extends f, we say that H acts homogeneously on Γ.

Kupitz and Perles proved

0.2 Theorem: If Γ is a finite, connected bipartite graph of girth 4 which is not complete, and is locally 3-symmetric, then |L| = |R|.

We shall also need some standard set theoretic notation: ω is the set of all natural numbers. We use the convention that n = {0, 1, …, n − 1}, namely that a natural number equals the set of all smaller natural numbers. By ^{ω}ω we denote all functions from ω to ω and by ^{<ω}ω we denote all finite sequences from ω. ^{n}ω is the set of all sequences of natural numbers of length n, i.e., functions from n into ω. For η ∈ ^{n}ω, i ∈ ω we let η i be the sequence η extended by i, i.e., η ∪ {⟨n, i⟩}.

The relation η ◁ ν between the sequences η and ν denotes that η is an initial segment of ν. Ord is the class of ordinals. An ordinal is equal to the sets of all smaller ordinals, α = {β ∈ Ord : β < α}.

By f[A] we denote the range of the function f when restricted to the set A. An n-tuple \overline{x} of a set A is an ordered subset \{x(1), x(2), …, x(n)\} ⊆ A of size n. By |A| we denote the cardinality (finite or infinite) of the set A. By domf we denote the domain of a function f and by ranf its range. If A ⊆ ω, the complement of A (in ω) is the set ¬A =^{def} ω \ A.

The symbol ∀^{∞}x ∈ A means “for all but finitely many x in A”.

§1. What Homogeneous Bipartite Graphs Exist? Let us classify all bipartite homogeneous graphs. Suppose Γ = ⟨L, R, E⟩ is homogeneous. If both sides are of cardinality 1, there are only two possibilities. Suppose then that x ≠ y are on the same side (say L). If Γ(x) = Γ(y), by homogeneity Γ(x) = Γ(z) for every z ∈ L, or, in other words, there is a set B ⊆ R such that B = Γ(x) for all x ∈ L. If B and R \ B are proper subsets of R, an easy violation of homogeneity follows. Therefore Γ is either a complete or an empty bipartite graph.

Thus, if Γ is neither complete nor empty, it must be that x = y ⇔ Γ(x) = Γ(y) for every x, y ∈ L and for every x, y ∈ R (a graph which satisfies this equivalence is called extensional).

Let us first assume that for some x ∈ L, Γ(x) is a finite subset of R of cardinality n. By homogeneity, {Γ(x) : x ∈ L} = {u : u ⊆ R, |u| = n}. If n > 1 and |R| > n + 1, this leads to a contradiction (try mapping two x-s with n − 1 common neighbors to two other x-s with n−2 common neighbors). If |R| = n+1, Γ is a complement of a perfect matching of size 2n + 2. So we are left with the case n = 1. One possibility is that R = {u}, and in this case Γ is a complete bipartite graph. Otherwise, Γ must be a perfect matching! Similarly, if Γ(x) is co-finite for some x ∈ L, then Γ is a complement of a perfect matching. All this applies when L is replaced by R.

We are left, then, with the case that every x ∈ L has an infinite co-infinite set of neighbors in R and vise versa. In this case we prove that Γ satisfies for every k, l < ω the following property:

(∗)_{k,l} For every distinct x_{0}, ⋯, x_{k}, y_{0}, ⋯, y_{l} in L (in R) there are infinitely many u ∈ R (in

L) such that u ∈ Γ(x_{i}) and u ∉ Γ(y_{j}) for i ≤ k, j ≤ l. Proof: Given x_{0}, …, x_{k}, y_{0}, …, y_{l} ∈ L, let us first prove that there is at least one u ∈ R which is a neighbor of every x_{i} and not a neighbor of every y_{j} for i ≤ k, j ≤ l. Let v ∈ R be any vertex. Pick distinct x′_{0}, ⋯, x′_{k} ∈ Γ(v) and y′_{0}, ⋯, y′_{l} ∉ Γ(v) from L. This is possible, since Γ(v) is infinite co-infinite. Now find an automorphism φ that takes x′_{i}, y′_{j} to x_{i}, y_{j} respectively, and u := φ(v) is as we want. Next suppose that there are x_{i}, y_{j} as above for which there are only finitely many u as above, and suppose, furthermore that the number of such elements u is minimal for this choice of x_{i}, y_{j}. As L is infinite, there is some z ∈ L, z ≠ x_{i} and z ≠ y_{j} for i ≤ k and j ≤ l. Let u be as above. If u ∈ Γ(z) let z := y_{l+1}, and otherwise let z := x_{k+1} to obtain a choice of x_{i}, y_{j} with a smaller number of u, and a hence a contradiction.

We call a bipartite graph which satisfies (∗)_{k,l} for all k, l < ω ran dom, and state without proof: 1.1 Fact: Every countable random bipartite graph is homogeneous and has girth 4. 1.2 Fact: Every two countable random bipartite graphs are isomorphic to each other.

For proofs see [ES] p.98 or [CK] p. 93 and p.129.

1.3 Remark: As a consequence of 1.2, the set of sentences {(∗)_{k,l} : k, l < ω} is a set of axioms of a complete first-order theory (see [CK] p. 113). Also, the sentences in this theory are exactly those sentences whose probability to hold in a randomly chosen bipartite graph of size 2n tends to 1 when n tends to infinity.

Let us sum up what homogeneous bipartite graphs there are: () complete bipartite graphs and empty bipartite graphs. () perfect matchings and complements of perfect matchings. () homogeneous random bipartite graphs.

Evidently, it is class (c) that deserves attention. By the remark above, all members of class (c) are elementarily equivalent to each other (i.e., satisfy the same first-order sentences). We already mentioned that the countable members of class (c) are all isomorphic to the countable random bipartite graphs, so we might ask: 1.4 Question: What uncountable homogeneous bipartite graphs are there? As (a) and (b) are trivial, the question is what uncountable members of class (c) are there?

We shall now show that there are homogeneous random graphs with countable left side and uncountable right side. We call these graphs (ℵ_{0}, κ) saS graphs when the cardinality of their right side is κ > ℵ_{0}. Recall that above we showed that if a homogeneous bipartite graph is neither complete nor empty then it is extensional. This implies in particular that |L| ≤ 2^{|R|} and |R| ≤ 2^{|L|}. Therefore if in a homogeneous non-trivial bipartite graph |L| = ℵ_{0}, we have an a priori bound of 2^{ℵ_{0}} on |R|. We shall see that this bound is attained: 1.5 Theorem: There is an (ℵ_{0}, 2^{ℵ_{0}}) saS graph. Proof: The left side of our graph will be ω, and the right side will be a set of functions in ^{ω}ω. We will construct our graph as a projective limit, in some appropriate sense, of a sequence ⟨Γ_{n} : n < ω⟩ of finite bipartite graphs.

We shall need the following notion: 1.6 Definition: We say that Γ′ is a “magic extension” of Γ if

(1) Γ is an induced subgraph of Γ′.

(2) Every finite partial automorphism of Γ extends to a total automorphism of Γ′.

E. Hrushovski proved in [H] the following theorem: 1.7 Theorem: Every finite graph has a finite magic extension.

Looking at the proof in [H] one can see that the same theorem is still true if we replace “finite graph” by “finite bipartite graph”. Hence, we get the following fact: 1.8 Fact: For every finite bipartite graph Γ there is a finite bipartite magic extension Γ′.

The fact follows also from a more recent result by Herwig on magic extensions of finite relational structures see [HE].

We remark here that it is only the finite case that needed a proof, because it is standard and easy that every infinite (bipartite) graph has a magic extension of the same cardinality. (see [CK, p. 214ff])

Proof of 1.5: We define now the construction of the sequence ⟨Γ_{n} : 1 ≤ n < ω⟩. The graph Γ_{n} = ⟨L_{n}, R_{n}, E_{n}⟩ has a left side L_{n} which is an initial segment of ω (a natural number) and a right side R_{n} ⊆ ^{n}ω, a finite set of sequences of natural numbers of length n. Let L_{1} = {0, 1} and R_{1} = {⟨1⟩, ⟨2⟩} and E_{1} = {(0, ⟨1⟩), (1, ⟨2⟩)}. (This will ensure that the graph we get at the end is neither empty nor complete).

We demand:

(1) L_{2i+1} = L_{2i}

(2) R_{2i+1} = {η 1 : η ∈ R_{2i}}∪{η 2 : η ∈ R_{2i}} and for every x ∈ L_{2i+1} = L_{2i} and ν ∈ R_{2i+1}, {x, ν} ∈ E_{2i+1} ⇔ {x, ν(2i)} ∈ E_{2i} So at even stages we “double” the points of the right side. Put more precisely, we can

define ρ_{2i}(η) = η 1 for all η ∈ R_{2i}, π_{2i}(η) = η2i for η ∈ R_{2i+1}, and we let π_{2i} and ρ_{2i} be the identity on L_{2i}. Thus, although Γ_{2i} is not an induced subgraph of Γ_{2i+1}, ρ_{2i}, is an embedding of Γ_{2i} in Γ_{2i+1} as an induced subgraph, and π_{2i} is a graph homomorphism.

At odd stages 2i + 1, we do the following: Let ρ_{2i+1}(η) = η 1 for η ∈ R_{2i+1}, ρ_{2i+1} = identity on L_{2i+1}. Now find a magic extension Γ_{2i+2} = ⟨L_{2i+2}, R_{2i+2}, E_{2i+2}⟩ of the graph ρ[Γ_{2i+1}]. By renaming vertices we may assume that all vertices in R_{2i+2} which are not already in ρ_{2i+1}[Γ_{2i+1}] are sequences of length 2i + 2 whose first 2i + 1 entries are all 0, and that L_{2i+2} is an initial segment of the natural numbers.

Again we let π_{2i+1}(η) = η(2i + 1) for all η ∈ ρ(R_{2i+1}), π(x) = x for x ∈ L_{2i+1}. So π is a partial homomorphism from Γ_{2i+2} onto Γ_{2i+1}.

Note that our sequence of graphs, together with the maps π_{i} can be viewed almost as a projective system, except that the homomorphism involved are partial. Nevertheless, its “projective limit” can be defined in a natural way:

We define Γ_{∞} = (L, R, E) as follows: The left side L = ω. The right side R = {η ∈ ωω : (∀^{∞}n)(ηn ∈ R_{n})}. Let E = {{x, η} : (∀^{∞}n)({x, ηn} ∈ E_{n})}.

We have to show two facts: 1.9 Fact: The cardinality of R is 2^{ℵ_{0}}.

1.10 Fact: The graph Γ_{∞} = ⟨L, R, E⟩ is homogeneous.

The proof of the first being trivial, let us turn to the proof of the second. Suppose f is a finite partial automorphism of Γ. We can find n_{0} which is large enough such that (domf ∪ ranf) ∩ L ⊆ L_{n_{0}} and such that for any η_{1} ≠ η_{2} in domf ∪ ranf, η_{1}n_{0}, η_{2}n_{0} ∈ R_{n_{0}} and η_{1}n_{0} ≠ η_{2}n_{0}, and such that for every x, η ∈ domf∪ranf, {x, η} ∈ E ⇔ {x, ηn_{0}} ∈ E_{n_{0}}. So for each n ≥ n_{0}, f induces a (finite) partial automorphism f_{n} of Γ_{n}: f_{n}(ηn) = f(η)n for all η ∈ dom(f) ∩ R, f_{n}(x) = f(x) for x ∈ dom(f) ∩ L. Suppose without loss of generality that n_{0} = 2i_{0} + 1. Let f̄_{n_{0}} = f_{n_{0}}. Now argue by induction on n ≥ n_{0} to get a sequence of partial automorphisms (f̄_{n} : n ≥ n_{0}) satisfying the following for all n ≥ n_{0}:

(1) f̄_{n} is a partial automorphism of Γ_{n}, and if n > n_{0}, then f̄_{n} is total.

(2) f̄_{n} extends f_{n}.

(3) π_{n} ∘ f̄_{n+1} = f̄_{n} ∘ π_{n} Given f̄_{2i−1} (i > n_{0}), a partial automorphism on Γ_{2i−1}, we can find a total auto-

morphism f̄_{2i} of Γ_{2i} extending f̄_{2i−1} (or more precisely, extending π_{2i−1}^{−1} ∘ f_{2i−1} ∘ π_{2i−1}). Condition (2) will automatically be satisfied.

Now we have to define f̄_{2i+1}. We must have f̄_{2i+1}L_{2i+1} = f̄_{2i}L_{2i}, so it remains to define f̄_{2i+1}R_{2i+1}. To satisfy condition (3), we require

(∗) if f̄_{2i}(x) = y, then f̄_{2i+1}[{x 1, x 2}] = {y 1, y 2}.

For x in dom(f_{2i}) ∩ R_{2i}, exactly one of x 1, x 2 is in dom(f_{2i+1}) (by our assumption on n_{0}), so (2) and (3) uniquely determine the behaviour of f̄_{2i+1} on x 1 and x 2 in this case. For η ∉ dom(f_{2i}), we define f̄_{2i+1}(η) arbitrarily satisfying (∗).

Having done the induction, let F be defined of Γ as follows: for x ∈ ω, F (x) = y ⇔ (∀^{∞}n)(f̄_{n}(x) = y) and for η ∈ R, F (η) = ν ⇔ (∀^{∞}n)(f̄_{n}(ηn) = νn).

We have to check that this indeed defines an automorphism. Note that all the f̄_{i} extend each other as far as the left side is concerned, and that whenever η ∈ R_{i}, j < i and ηj ∈ R_{j}, then f̄_{i}(η)j = f̄_{j}(ηj). From this property it is easy to see that all F is well-defined on the right side of Γ, and since all the f̄_{i} are automorphism, also f̄ will be an automorphism. _{⌣} · · 1.91.101.5

We do mention one more thing: The proof actually gave us the following property:

(∗∗) for every finite partial automorphism f of Γ there is a locally finite automorphism F of Γ extending f.

By a locally finite automorphism we mean a permutation F of Γ with the property that for every finite A ⊆ ω there is a finite B ⊇ A such that F B ∈ Sym(B).

1.11 Remark: (1) A similar proof shows the existence of (κ, 2^{κ}) saS graphs for any infinite cardinal κ.

(2) If κ < λ′ ≤ λ, and if Γ is a (κ, λ) saS graph, then it is easy to find an induced subgraph Γ′ which is a (κ, λ′) saS graph.

§2. The number of (ℵ_{0}, ℵ_{1}) saS graphs under weak CH

In this section we handle the question of the number of the isomorphism types of (ℵ_{0}, ℵ_{1}) saS graphs. An obvious upper bound is 2^{ℵ_{1}}, the number of isomorphism types of graphs of size ℵ_{1}. In this section we show that if 2^{ℵ_{0}} < 2^{ℵ_{1}}, then this upper bound is realized: there are 2^{ℵ_{1}} isomorphism types of (ℵ_{0}, ℵ_{1}) saS graphs. In the next section we show that if CH fails a nd MA holds, then all (ℵ_{0}, ℵ_{1}) saS graphs are isomorphic to each other, namely there is a unique isomorphism type of (ℵ_{0}, ℵ_{1}) saS graphs.

The idea of the first proof is as follows: we construct a family G of 2^{ℵ_{1}} different saS graphs sharing the same fixed countable left side. An isomorphism between two saS graphs being determined by its action on the left side, an isomorphism between two saS graphs in G is really a permutation of the left side. There are 2^{ℵ_{0}} permutations of a given countable set, therefore there are at most 2^{ℵ_{0}} members in every equivalence class of G modulo isomorphism. Therefore it follows by 2^{ℵ_{0}} < 2^{ℵ_{1}} that there are 2^{ℵ_{1}} such classes.

The construction of many different saS graphs is done by iteratively extending a countable random graph ω_{1} many times, preserving homogeneity and preserving the left side, in 2^{ℵ_{1}} many different ways.

2.1 Notation: The left side of all graphs in this section will be ω. Since we deal only with extensional graphs, we will identify a vertex in R with its set of neighbors in L, so the edge relation will always be given by ∈. For u ∈ R denote u^{+} =^{def} u and u^{−} =^{def} ¬u.

For a finite function σ : R → {+, −} we let B_{σ} = ⋂_{u∈domσ} u^{σ(u)}. If Γ is random, then for every finite function σ : R → {+, −} the set B_{σ} is infinite.

We now prove a few technical lemmas concerning the structure of the automorphism group of a random bipartite graph, which will be used later in extending countable random bipartite graphs: 2.2 Lemma: Suppose that Γ = ⟨ω, R, ∈⟩ is random, that u_{0}, …, u_{k} ∈ R and that f, g ∈ Aut(Γ) are two distinct automorphisms of Γ. Then there are u, v ∈ R, both not in the list u_{0}, …, u_{k} such that for every x ∈ u \ v, f(x) ≠ g(x).

What this lemma says is, that if two automorphisms are different, then they are different on a definable infinite set of vertices: the set of all points which are connected to some u and not connected to some v. Moreover, the u and v may be chosen quite freely. Proof: We may assume by applying g^{−1} to f and g, that g = id. As f ≠ id, there is some x such that f(x) ≠ x. As Γ is random, there are infinitely many u ∈ Γ which satisfy x ∈ u but f(x) ∉ u. Pick one such u with the property that both u and f(u) are not in the list u_{0}, …, u_{κ} and set v := f(u). For every x ∈ u, f(x) ∈ v. So if x ∈ u \ v, f(x) ∈ v, while x ∉ v. In particular, f(x) ≠ x. _{⌣} · · 2.2

2.3 Corollary: If Γ is random, u_{0}, …, u_{k} ∈ R and g_{1}, g_{2}, …, g_{l} ∈ Aut(Γ) then there is some finite function σ : R → {+, −} such that {u_{0}, …, u_{k}} ∩ domσ = ∅, and such that for every x ∈ B_{σ}, g_{1}(x), g_{2}(x), …, g_{l}(x) are l distinct members of ω. Proof: Apply 2.2 iteratively \binom{l}{2} times. _{⌣} · · 2.3

2.4 Lemma: Suppose that B is an infinite subset of ω and that g_{1}, …, g_{k} are 1-1 functions defined on B with the property that for every x ∈ B and 1 ≤ i < j ≤ k, g_{i}(x) ≠ g_{j}(x). Then there is an infinite subset B′ ⊆ B such that for every x ≠ y in B′ and 1 ≤ i ≤ j ≤ k, g_{i}(x) ≠ g_{j}(y) Proof: By induction on n we pick an increasing chain of finite sets A_{n} with this property. At the induction stage: Clearly g_{i}^{−1}[A_{n}] is finite, because g_{i} is 1-1. Pick any x ∈ B \ {g_{i}^{−1}[g_{j}[A_{n}]] : 1 ≤ i ≤ j ≤ k} and let A_{n+1} = A_{n} ∪ {x}. _{⌣} · · 2.4

2.5 Corollary: Suppose that Γ is random, τ : Γ → {+, −} is a finite partial function, and G ⊆ Aut(Γ) is finite. Then there exists an infinite set B ⊆ B_{τ} such that for (g, x) ≠ (g′, x′) ∈ G × B, g(x) ≠ g′(x′). Proof: By Corollary 2.3 there is a finite function σ : R → {+, −} such that for every x ∈ B_{σ}, the elements G(x) are |G| distinct elements. As domτ and domσ are disjoint, also τ ∪ σ is a function and therefore B_{τ∪σ} ⊆ B_{σ} is infinite. By Lemma 2.4 there is an infinite set B ⊆ B_{σ∪τ} for which the required holds. _{⌣} · · 2.5

We now prove the main lemma: 2.6 Lemma: Suppose Γ is a countable random bipartite graph, and G ⊆ Aut(Γ) is a countable group of automorphisms. Then there are two incompatible countable random bipartite graphs Γ^{0} and Γ^{1} with the same left side as Γ, properly extending Γ such that G ⊆ Aut(Γ^{i}) for i ∈ {0, 1}. By “incompatible” we mean that there is no random bipartite graph Γ′ with the same left side as Γ extending both Γ^{0} and Γ^{1}.

Proof: For any set S ⊆ ω, the graph Γ^{0} = ⟨ω, R ∪ G(S), ∈⟩ satisfies that G ⊆ Aut(Γ)), where G(S) denotes {g[S] : g ∈ G} and g[S] = {g(x) : x ∈ S}. But Γ^{0} is not necessarily random for an arbitrary choice of S (for example, it is not random if S = ¬A for some A ∈ R). We shall find some subset S of ω such that both Γ^{0} := ⟨ω, R ∪ G(S), ∈⟩ and Γ^{1} = ⟨ω, R ∪ G(¬S) ∈⟩ are random. This will complete the proof, as in addition to the fact that Γ^{i} is random and G ⊆ AutΓ^{i} (i = 0, 1), it is clear that there is no random graph Γ′ = ⟨ω, R′, ∈⟩ such that both S and ¬S belong to R′.

For a, b ⊆ ω, a ∩ b = ∅ and any finite partial function σ : G ∪ R → {+, −} we let

B_{σ,a,b} =^{def} ⋂_{A∈R∩dom(σ)}A^{σ(A)} ∩ ⋂_{g∈G∩σ^{−1}(+)}g(a) ⋂_{g∈G∩σ^{−1}(−)}g(b)

So our goal is to construct a set S such that for all σ as above we have

B_{σ,S,¬S} is infinite

This is equivalent to saying that ⟨ω, R ∪ G(S), ∈⟩ and by symmet ry also ⟨ω, R ∪ G(¬S) ∈⟩ are random.

Note that there are only countably many finite partial functions σ as above, so we can enumerate them as σ_{1}, σ_{2}, . . .. We may also assume that each such σ occurs infinitely many times in this list.

We construct S and ¬S by approximating them inductively by finite sets a_{n} ⊆ S and b_{n} ⊆ ¬S, which satisfy

(i) a_{n} ∩ b_{n} = ∅. (ii) n ∈ a_{n+1} ∪ b_{n+1} (iii) a_{n} ⊆ a_{n+1} and b_{n} ⊆ b_{n+1} (iv) There are at least n points in B_{σ_{n},A_{n+1},b_{n+1}}.

For n = 0 let a_{n} = b_{n} = ∅.

For n + 1: We specify which elements should be added to a_{n} and b_{n} to obtain a_{n+1} and b_{n+1} respectively.

First, if n ∉ a_{n} ∪ b_{n}, add it to a_{n+1}.

We can find by 2.5 an infinite set B ⊆ B_{σ_{n}R} such that for all (g, x) ≠ (g′, x′) in (dom(σ ∩ G)) × B, g(x) ≠ g′(x′).

Now note that B_{n} =^{def} {g(x) : x ∈ a_{n} ∪ b_{n}, g ∈ dom(σ_{n}) ∩ G} is finite, so we can find a set X_{n} ⊆ B \ (B_{n} ∪ {n}) of size n.

Let a_{n+1} =^{def} a_{n} ∪ {g^{−1}(x) : g ∈ σ^{−1}(+) ∩ G, x ∈ X_{n}}, and let b_{n+1} =^{def} b_{n} ∪ {g^{−1}(x) :

g ∈ σ^{−1}(−) ∩ G, x ∈ X_{n}}. Note that a_{n+1} and b_{n+1} are disjoint, by the conclusion of 2.5. Moreover, B_{σ_{n},a_{n+1},b_{n+1}} ⊇ X_{n} and therefore (iv) holds.

Let S = ⋃_{n} a_{n}. It follows by (i) that ¬S = ⋃_{n} b_{n}. As for any S ⊆ ω, if a_{n+1} ⊆ S and b_{n+1} ⊆ S, then

B_{σ_{n},S,¬S} ⊇ B_{σ_{n},a_{n+1},b_{n+1}} ⊇ X_{n}

Since each finite partial σ : G ∪ R → {+, −} appears as σ_{n} with arbitrarily large n, this shows that B_{σ,S,¬S} is infinite. _{⌣} · · 2.6 2.7 Theorem: There are 2^{ℵ_{1}} different homogeneous random bipartite graphs of cardinality ℵ_{1} with ω as their left side. Proof: To every η ∈ ^{<ω_{1}}2 we attach a pair ⟨Γ_{η}, G_{η}⟩ such that the following conditions hold:

(1) Γ_{η} = ⟨ω, R_{η}, ∈⟩ is a countable random bipartite graph and G_{η} ⊆ AutΓ_{η} is a countable group that acts on Γ_{η} homogeneously.

(2) If η ◁ ν then R_{η} ⊆ R_{ν} and G_{η} ⊆ G_{ν}.

(3) For every η, R_{η 0} and R_{η 1} are incompatible.

We define ⟨Γ_{η} and G_{η}⟩ by induction on the length of η. If η is the empty sequence, let Γ_{η} be any countable random bipartite graph with ω as its left side, and let G_{η} be any countable group of automorphisms that acts homogeneously on Γ_{η}.

If lg η is some limit ordinal α, let R_{η} = ⋃_{β<α} R_{ηβ} and let G_{η} = ⋃_{β<α} G_{ηβ}. We should show that that G_{η} ⊆ Aut(Γ_{η}) and that it acts homogeneously on Γ_{η}. As all members of G_{η} preserve ∈ by their definition on R_{η}, it is enough to show that R_{η} is closed under G_{η}. Suppose that g ∈ G_{η} and A ∈ R_{η} are arbitrary. There is some β < lg(η) such that g ∈ G_{ηβ} and A ∈ R_{ηβ}. Now g(A) ∈ R_{ηβ} ⊆ R_{η}. To see homogeneity, suppose f is a finite partial automorphism of Γ_{η}. There is some ordinal β < lg η such that domf ∪ ranf ⊆ ω ∪ R_{ηβ}. By the induction hypothesis, there is some g ∈ G_{ηβ} ⊆ G_{η} extending f.

If ⟨Γ_{η}, G_{η}⟩ is defined, use lemma 2.6 to find two incompatible countable homogeneous random bipartite extensions of Γ_{η}, Γ_{η 0} and Γ_{η 1}. As Γ_{η i} are countable random bipartite graphs for i ∈ {0, 1}, they are homogeneous by fact 1.1. For every finite partial automorphism of Γ_{η i} there is an automorphism of Γ_{η i} which extends it, so by adding countably many automorphisms to G_{η} and closing under composition we get a countable group extending G_{η} which acts homogeneously on Γ_{η i}. Let this group be G_{η i}.

Having done the definition by induction, we define for every sequence ξ ∈ ^{ω_{1}}2 a bipartite graph Γ_{ξ} = ⟨ω, ⋃_{α<ω_{1}} R_{ξestα}, ∈⟩. As the group G_{ξ} = ⋃_{α<ω_{1}} G_{ξα} acts homogeneously on Γ_{ξ} — as is easily seen — Γ_{ξ} is homogeneous. Suppose that ξ_{0} and ξ_{1} are two different members of ^{ω_{1}}2 and let α be the last ordinal such that ξ_{0}α = ξ_{1}α. By condition (3) above, ⟨ω, R_{ξ_{0}}, ∈⟩ ⟨ω, R_{ξ_{1}}, ∈⟩ are incompatible. As Γ_{ξ_{0}} and Γ_{ξ_{1}} are random, they must be different. _{⌣} · · 2.7

2.8 Theorem: If 2^{ℵ_{0}} < 2^{ℵ_{1}}, then there are 2^{ℵ_{1}} many isomorphism types of (ℵ_{0}, ℵ_{1}) saS graphs. Proof: By the previous theorem there is a collection of 2^{ℵ_{1}} many different saS graphs {Γ_{i} : i < 2^{ℵ_{1}}} such that the left side of each Γ_{i} is ω. An isomorphism between Γ_{i} and Γ_{j} for i, j < 2^{ℵ_{1}} is determined by its action on ω. Therefore in an equivalence class of {Γ_{i} : i < 2^{ℵ_{1}}} modulo isomorphism there are at most 2^{ℵ_{0}} members. By the assumption 2^{ℵ_{0}} < 2^{ℵ_{1}}, it follows that there are 2^{ℵ_{1}} many equivalence classes. _{⌣} · · 2.8

2.9 Remark: The proof above is readily generalized to give 2^{κ^{+}} isomorphism types of (κ, κ^{+}) saS graphs in case 2^{κ} < 2^{κ^{+}}.

We note that CH implies that 2^{ℵ_{0}} < 2^{ℵ_{1}}, and therefore implies by the theorem above that there are 2^{ℵ_{1}} many isomorphism types of (ℵ_{0}, ℵ_{1}) saS graphs.

§3. The number of (ℵ_{0}, ℵ_{1}) saS graphs under the MA + ¬CH

We turn now to an examination of the number of (ℵ_{0}, ℵ_{1}) saS graphs under the assumption that CH fails but Martin’s axiom MA holds. The situation here is exactly opposite to what we have seen under (weak) CH. We shall prove the following: 3.1 Theorem (MA): For any κ < 2^{ℵ_{0}} there is a unique (ℵ_{0}, κ) saS graph.

First we will recall the statement of MA (see [K]):

A dense set D in a partial order (P, ≤) is a subset D ⊆ P such that for every x ∈ P there is y ∈ D, x ≤ y. Two members x, y ∈ P are compatible if there is z ∈ P such that x ≤ z and y ≤ z. An antichain in P is a set of pairwise non compatible elements. A partial order satisfies the ccc (countable chain condition) if every antichain is countable. A filter in a partial order is a set F ⊆ P which satisfies (a) F is downward closed, i.e. y ∈ F & x ≤ y ⇒ x ∈ F and (b) F is directed, i.e. x, y ∈ F ⇒ (∃z ∈ F)(z ≥ x & z ≥ y). The axiom MA (Martin’s Axiom) is the statement “for every ccc partial order P and every collection 𝔇 of fewer than 2^{ℵ_{0}} dense sets of P there is a filter of P with non-empty intersection with every D ∈ 𝔇”. MA follows easily from the continuum hypothesis (CH), but it is known that MA is consistent with the negation of CH — in fact, MA may be true with the continuum being any regular cardinal.

Let us introduce the following notation: if Γ = (ω, R, E) is a bipartite graph, σ a finite partial function from ω to {+, −} we let

B_{σ} := {a ∈ R : ∀x ∈ dom(σ) : σ(x) = + iff {x, a} ∈ E}

3.2 Lemma: Let Γ = ⟨ω, R, E⟩ be an (ℵ_{0}, κ) saS graph, κ > ℵ_{0}. Then for all σ as above we have |B_{σ}| = κ. Proof: Fix k, l in ω. We will only consider functions σ with |σ^{−1}(+)| = k, |σ^{−1}(−)| = l. For any such functions σ, σ′ there is a partial automorphism f mapping σ^{−1}(+) to σ′^{−1}(+) and σ^{−1}(−) to σ′^{−1}(−). The total automorphism f̄ extending f must map B_{σ} onto B′_{σ}.

Hence all these sets B_{σ} have the same cardinality, say λ. Since since every element of R must be in some such B_{σ} (by homogeneity) and there are only countably many such σ we get κ ≤ λ · ℵ_{0}, i.e., λ = κ. _{⌣} · · 3.2

3.3 Fact: If Γ = ⟨ω, R, E⟩ is an (ℵ_{0}, κ) saS graph, then R can be partitioned into κ many countable sets (R_{i} : i < κ) such that for all i < κ the induced subgraph determined by (ω, R_{i}) is random. Proof: Let R = {x_{i} : i < κ}. We will construct (R_{i} : i < κ) by induction. Given (R_{j} : j < i), we can choose countable sets

R_{i}^{σ} ⊆ B_{σ} \ ⋃_{j<i} R_{j}

for every partial finite function σ from ω to {+, −}, because by 3.2, |B_{σ}| = κ, | ⋃_{j<i} R_{j}| < κ. If x_{i} ∈ ⋃_{j<i} R_{j} then let

R_{i} := ⋃_{σ} R_{j}^{σ}

otherwise let R_{i} := ⋃_{σ} R_{j}^{σ} ∪ {x_{i}}. _{⌣} · · 3.3 3.4 Definition: Assume Γ = ⟨ω, R, E⟩ and Γ′ = ⟨ω, R′, E′⟩ are two (ℵ_{0}, κ) saS graphs, and let R = ⋃_{i} R_{i}, R′ = ⋃_{i} R′_{i} be partitions as in 3.3. We let P_{Γ,Γ′} be the set of all finite partial isomorphisms between Γ and Γ′ respecting the partitions, i.e., all finite partial isomorphisms p satisfying

∀x ∈ dom(p) ∩ R_{i} : p(x) ∈ R′_{i}

P_{Γ,Γ′} is naturally ordered by the set inclusion relation. (We consider functions to be sets of ordered pairs.)

3.5 Lemma: (P_{Γ,Γ′}, ⊆) is a partial order satisfying the countable chain condition.

Proof: Let {p_{α} : α < ω_{1}} ⊆ P_{Γ,Γ′}. For each α let s_{α} := {i < κ : dom(p_{α}) ∩ R_{i} ≠ ∅}. s_{α} is a finite set. Applying the Δ-system lemma [K, II, 1.5] we may without loss of generality assume that (s_{α} : α < ω_{1}) forms a Δ-system with root s. Moreover, since there are only countably many possibilities for p_{α}s, we may also assume that for some p ∈ P_{Γ,Γ′} we have for all α: p_{α}s = ps. Similarly, we may assume p_{α}ω = pω for all α. Now for any α, β we have that p_{α} ∪ p_{β} is a 1-1 function, and hence an element of P_{Γ,Γ′} _{⌣} · · 3.5

3.6 Proof of 3.1: Let Γ = ⟨ω, R, E⟩, Γ′ = ⟨ω, R′, E′⟩ be (ω, κ) saS graphs, and fix partitions as in 3.3. For any filter G ⊆ P_{Γ,Γ′}, we let f_{G} := ⋃ G. Clearly f_{G} will be a partial isomorphism from Γ to Γ′.

Now note that for each x ∈ ω ∪ R, the set D_{x} := {p ∈ P_{Γ,Γ′} : x ∈ dom(p)} is a dense subset of P_{Γ,Γ′} (because each (ω, R′_{i}) is a random bipartite graph).

By MA we can find a filter G ⊆ P_{Γ,Γ′} that meets all D_{x}. This implies that f_{G} is an isomorphism from Γ into Γ′. Similarly, using κ many dense sets defined from Γ′ we can insure that f will be onto. Hence Γ and Γ′ are isomorphic. _{⌣} · · 3.1

Goldstern, Grossberg, Kojman: Bipartite Graphs

References:

[B] J. Baumgartner,All ℵ_{1}-dense sets of reals can be isomorphic, Fundamenta Mathematicae vol. 79 (1971). pp. 101–106.

[C] G. Cherlin, Homogeneous Tournaments revisited, Geometria Dedicata 26 (1988), 231–240.

[CK] C. C. Chang and H. J. Keisler, Model Theory, North Holland, 1973.

[ES] P. Erdős and J. Spencer, Probabilistic Methods in Combinatorics, Academic Press 1974.

[HE] B. Herwig, Extending partial isomorphisms on finite structures, to appear in combinatorica

[H] E. Hrushovski, Extending partial isomorphisms of graphs, to appear in combinatorica

[K] K. Kunen, Set Theory: An introduction to independence proofs, North Holland, 1980

[KP] Kupitz and Perles, untitled, in preparation.

[L] A. Lachlan, Countable Homogeneous Tournaments, Trans. Amer. Math. Soc.

284 (1984), 431–461

[LW] A. H. Lachlan and R .E. Woodrow, Countable Ultrahomogeneous Undirected Graphs, Trans. Amer. Math. Soc. 262 (1980) 51–94.