October 31, 1997

SMOOTH GRAPHS

L. SOUKUP

Abstract. A graph G on ω_{1} is called < ω-smooth if for each uncountable W ⊂ ω_{1}, G is isomorphic to G[W \W′] for some finite W′ ⊂ W. We show that in various models of ZFC if a graph G is < ω-smooth than G is necessarily trivial, i.e, either complete or empty. On the other hand, we prove that the existence of a non-trivial, <ω-smooth graph is also consistent with ZFC.

1. Introduction

Answering a question of R. Jamison, H. A. Kierstead and P. J. Nyikos proved in [3]: if the uncountable induced subgraphs of an uncountable nuniform hypergraph are pairwise isomorphic, then the hypergraph must be either empty or complete. In this note we investigate how many uncountable subgraphs of a graph G on ω_{1} can be isomorphic to G provided that it is non-trivial, i.e. it is not complete or empty. As a corollary of [1, theorem 4.2] we can get the following positive result: the existence of a non-trivial graph on ω_{1} which embeds into each of its uncountable subgraphs is consistent with ZFC. To formulate this and the forthcoming results precisely we need the following definition.

d:smooth Definition 1.1. A graph G on ω_{1} is called κ-smooth (<κ-smooth) if for each uncountable W ⊂ ω_{1}, G is isomorphic to G[W \ W′] for some W′ ⊂ W with |W′| ≤ κ (|W′| < κ).

Fact 1.2. If a graph G on ω_{1} is n-smooth for some n ∈ ω, then G is complete or empty.

Proof. Pick ordinals x_{0}, x_{1}, …, x_{n} from ω_{1} by finite induction such that for each j ≤ n we have

x_{j} ∈ ⋂_{i<j} G(x_{i}) and |⋂_{i≤j} G(x_{i})| = ω_{1}.

1991 Mathematics Subject Classification. 03E35.

Key words and phrases. graph, isomorphic subgraphs, independent result, Cohen, forcing, iterated forcing.

The preparation of this paper was supported by the Hungarian National Foundation for Scientific Research grant no. 16391.

If we can not find a suitable x_{j} then taking W = ⋂_{i<j} G(x_{i}) we have |W | = ω_{1} but |W ∩ G(w)| ≤ ω for each w ∈ W. Thus G[W] contains an uncountable induced empty subgraph and so G is empty.

Assume now that we could choose the sequence {x_{i} : i ≤ n}. Then let W = {x_{i} : i ≤ n} ∪ ⋂_{i≤n} G(x_{i}). Since G is n-smooth there is W′ ⊂ W, |W′| ≤ n such that G ≅ G[W \ W′]. Fix i < n + 1 such that x_{i} ∉ W′. Since x_{i} ∈ W \ W′, W ⊂ G(x_{i}) ∪ {x_{i}} and G ≅ G[W \ W′] it follows that there is w ∈ ω_{1} such that ω_{1} ⊂ G(w) ∪ {w} and so for each uncountable V ⊂ ω_{1} there is v ∈ V such that |V \ G(v)| ≤ n. Thus G contains an uncountable complete subgraph and so G is complete.

On the other hand, in [1, theorem 4.2] it was shown that ♢^{+} implies that there is a Suslin tree T = ⟨ω_{1}, ≺⟩ such that for each uncountable X ⊂ ω_{1} there is a countable X′ ⊂ X such that T ≅ T |` (X \ X′). Thus the comparability graph of T is ω-smooth and clearly non-trivial. However, the question whether a <ω-smooth graphs on ω_{1} is necessarily trivial was left open. This gap will be filled up here: we show that (i) in different models of ZFC every <ω-smooth graph on ω_{1} is complete or empty, (ii) the existence of a non-trivial, <ω-smooth graph G on ω_{1} is consistent with ZFC.

The following question however remains unanswered:

Problem 1. Is there a non-trivial, ω-smooth or just ω_{1}-smooth graph on ω_{1} (in ZFC)?

We use the standard set-theoretical notation throughout, cf [2]. For a graph G, V (G) denotes the set of vertices of G, E(G) the family of edges of G. If H ⊂ V (G), G[H] denotes the induced subgraphs of G on H. Given x ∈ V (G) put G(x) = {y ∈ V (G) : {x, y} ∈ E(G)}. If G and H are graphs we write G ≅ H to mean that G and H are isomorphic.

If G and G′ are graphs, Iso_{p}(G, G′) denotes the family of isomorphisms between finite induced subgraphs of G and G′.

If q is a function let supp(q) = dom(q) ∪ ran(q).

For a cardinal κ we denote by C_{κ} the standard poset ⟨Fn(κ, 2; ω), ⊇⟩ which adds κ Cohen reals to the ground model.

2. Models without non-trivial <ω-smooth graphs

lm:half Lemma 2.1. If G is a <ω-smooth graph on ω_{1} and G has a — not necessarily spanned — subgraph isomorphic to the bipartite graph [ω; ω_{1}] then G is complete.

Proof. Fix A ∈ [ω_{1}]^{ω} and B ∈ [ω_{1}]^{ω_{1}} such that [A, B] ⊂ E(G). Let

X = {α ∈ ω_{1} : |ω_{1} \ G(α)| ≤ ω}.

We show that X is uncountable. Indeed, let α < ω_{1}. Then for some finite C ⊂ A∪B and D ⊂ ω_{1} \α the graphs G[(A∪B)\C] and G[(ω_{1} \ α)\D] are isomorphic witnessed by a function f. Then f′′(A\C) ⊂ X, so X ⊄ α, i.e. |X| = ω_{1}.

Now, by recursion, we can construct a set Y = {y_{η} : η < ω_{1}} ∩ X such that y_{η} ∈ X ∩ ⋂_{ξ<η} G(y_{ξ}). Then G[Y] is complete and so G is also

complete which was to be proved.

Let us remark that the statement of lemma 2.1 fails for ω-smooth graphs: the comparability graph G of the Suslin tree T constructed in [1, theorem 4.2] is non-trivial and ω-smooth, but [ω; ω_{1}] ⊂ G and [ω_{1}; ω_{1}] ⊂ \overline{G}.

Let us recall the definition of splitting number 𝔰:

𝔰 = min{|A| : A ⊂ [ω]^{ω}∧∀X ∈ [ω]^{ω} ∃A ∈ A |X∩A| = |X\A| = ω}.

tm:no-ko Theorem 2.2. Every <ω-smooth graph on ω_{1} is trivial provided (1) or (2) or (3) below hold:

kofelt-1 (1) ω_{1} < 𝔰,

kofelt-2 (2) 2^{ω} < 2^{ω_{1}}, kofelt-3 (3) in a model obtained by adding ω_{2} Cohen reals to some model V.

Proof of theorem 2.2(1). Assume that G is <ω-smooth. For each α ∈ ω_{1} let F_{α} = G(α) ∩ ω. The family F = {F_{α} : α < ω_{1}} is not a splitting family for 𝔰 > ω_{1} so there is an infinite set B ⊂ ω such that B ⊂^{∗} F_{α} or B ⊂^{∗} ω \ F_{α} for each α ∈ ω_{1}. Then there is n ∈ ω and an uncountable I ⊂ ω_{1} such that either B \ n ⊂ F_{α} for each α ∈ I or B \ n ∈ ω \ F_{α} for each α ∈ I. Thus either [B \ n, I] ⊂ E(G) or [B \ n, I] ∩ E(G) = ∅, i.e [ω; ω_{1}] is a subgraph of either G or \overline{G}, and so G is trivial by lemma 2.1.

Proof of theorem 2.2(2). Assume on the contrary, that that G is <ωsmooth and non-trivial. By lemma 2.1, we can choose an uncountable set A ⊂ ω_{1} \ ω such that G(α) ∩ ω ≠^{∗} G(β) ∩ ω for each {α, β} ∈ [A]^{2}.

For each uncountable X ⊂ A fix a finite set C_{X} ⊂ ω_{1} and an isomorphism f_{X} between G[(ω∪X)\C_{X}] and G. Since 2^{ω} < 2^{ω_{1}} there are sets X, Y ∈ [A]^{ω_{1}} such that |X \ Y | ≥ ω, C_{X} = C_{Y} and f_{X} |` ω = f_{Y} |` ω. Let ξ ∈ X \ Y \ C_{X}. Then f = f_{Y}^{−1} ∘ f_{X} is an isomorphism between G[(ω∪X)\C_{X}] and G[(ω∪Y)\C_{Y}] such that f |` (ω\C_{X}) = id |` (ω\C_{X}). Taking η = f(ξ) we obtain that G(ξ) ∩ (ω \ C_{X}) = G(η) ∩ (ω \ C_{X}) which contradicts the choice of A because η ≠ ξ for ξ ∉ ran(f).

Proof of theorem 2.2(3). Assume that G is a graph on ω_{1} in V^{C_{ω_{2}}}. Fix α < ω_{2} such that G ∈ V^{C_{α}}. Since C_{ω_{2}} = C_{α} ∗ C_{ω_{2}\(α+ω_{1})} ∗ C_{[α,α+ω_{1})}, by lemma 2.1 it is enough to prove the following statement:

lm:ground-oo Lemma 2.3. If G is a graph on ω_{1}, [ω; ω_{1}] ⊄ G, \overline{G}, then G is not <ω-smooth in V^{C_{ω_{1}}}.

Proof of lemma 2.3. Applying lemma 2.1, we can find an uncountable A ⊂ ω_{1} \ ω such that G(α) ∩ ω ≠^{∗} G(β) ∩ ω for each {α, β} ∈ [A]^{2}. If G is the C_{ω_{1}}-generic filter over V, let X = {α ∈ A : ∃p ∈ G p(α) = 1}. We show that

1_{C_{ω_{1}}}^{∥}— “G and G[(ω ∪ Ẋ) \ Y] are not isomorphic

for any Y ∈ [ω_{1}]^{<ω}. ”

Assume on the contrary that p ∈ C_{ω_{1}}, Y ∈ [ω_{1}]^{<ω} and ḟ is a C_{ω_{1}}- name of a function such that

p^{∥}— “ḟ is an isomorphism between G and G[(ω ∪ Ẋ) \ Y]”.

Fix ω ≤ ν < ω_{1} such that dom(p)∪Y ⊂ ν, p^{∥}— “ḟ′′ν = ((ω∪Ẋ)\Y)∩ν” and p^{∥}— “ḟ |` ν ∈ V [G |` ν].” From now on we work in V [G |` ν]. Let h = f |` ν and B = h^{−1}(ω \ Y). Since G(α) ∩ ω ≠^{∗} G(β) ∩ ω for each {α, β} ∈ [A]^{2} it follows that if {ζ, ξ} ∈ [ω_{1} \ ν]^{2} then G(ζ) ∩ B ≠^{∗} G(ξ) ∩ B. Thus for each ξ ∈ ω_{1} \ ν we have

f(ξ) = α iff h′′(G(ξ) ∩ B) =^{∗} (G(α) ∩ ω).

Hence f |` (ω_{1} \ ν) can be defined in V [G |` ν] and so X \ ν ∈ V [G |` ν], which is impossible by the choice of X.

The proof of theorem 2.2 is complete.

The following theorem claims that if CH holds in the ground model, then the statement of lemma 2.3 can be strengthened: we can find a set in the ground model witnessing that G is not <ω-smooth in V^{C_{ω_{1}}}.

tm:oot-miss Theorem 2.4. If CH holds and G is a graph on ω_{1} such that [ω; ω_{1}] ⊄ G, \overline{G}, then there is an uncountable subset X of ω_{1} such that

V^{C_{ω_{1}}} ⊧ “G is not isomorphic to G[X \ Y] for any Y ∈ [ω_{1}]^{ω_{1}}”

The proof is quite long and technical, so we omit it.

3. Generic construction of a non-trivial <ω-smooth graph

tm:smooth Theorem 3.1. If 2^{ω_{1}} = ω_{2}, then there is a c.c.c poset P of size ω_{2} such that

V^{P} ⊧ there is a non-trivial, <ω-smooth graph G on ω_{1}.

Proof. We construct P = C ∗ P′ in two steps: in the first step, forcing with C = Fn(ω_{1}, 2; ω), we add ω_{1}-many Cohen reals to V to introduce our desired graph G. Then, in the second step, we add many isomorphisms between certain subgraphs of G to V^{C} to guarantee <ωsmoothness of G in V^{C∗P′}.

To simplify our notation we take C = Fn([ω_{1}]^{2}, 2; ω) and define the graph G on ω_{1} in V [G], where G is the C-generic filter over V, in the straightforward way:

{α, β} ∈ E(G) iff ∃p ∈ G p({α, β}) = 1.

If c ∈ C let supp c = ∪ dom c and G^{c} = ⟨supp c, c^{−1}{1}⟩. Let us remark that if c, c′ ∈ C, c ≤ c′ and dom c′ = [supp c′]^{2} then G^{c′} is a spanned subgraph of G^{c}.

To obtain P′ = P_{ω_{2}} we carry out a finite support iteration of c.c.c posets

⟨P_{α} : α ≤ ω_{2}, Q_{α} : α < ω_{2}⟩

in the following way: in the α^{th} step, we pick an uncountable set X_{α} of ω_{1} in the intermediate model V^{C∗P_{α}} and then we try to find a finite set Y_{α} and c.c.c poset Q_{α} such that

V^{C∗P_{α}∗Q_{α}} ⊧ “G and G[X_{α} \ Y_{α}] are isomorphic witnessed by a function f_{α}.”

The poset Q_{α} will consist of certain isomorphisms between finite subgraphs of G and G[X_{α} \ Y_{α}], ordered by the reverse inclusion. In other words, we force with certain finite approximations of an isomorphism between G and G[X_{α} \ Y_{α}].

The problem is the right choice of Q_{α} because we should meet two contradictory requirements. First, the poset Q_{α} should satisfy c.c.c and forcing with Q_{α} can not introduce an uncountable empty or complete subgraph of G, therefore Q_{α} can not contain too many elements. On the other hand, to guarantee that a Q_{α}-generic filter gives an isomorphism between G and G[X_{α}\Y_{α}] we need some density arguments, i.e. certain subsets of Q_{α} should be dense in Q_{α}, which involves that Q_{α} can not be too small. As it turns out, it will be quite easy to meet the first requirement, the hard part of the proof is how to cope with the second one.

Now assume that P_{α} is constructed and let us see the induction step. First, using a bookkeeping function, we pick the set X_{α} ∈ [ω_{1}]^{ω_{1}} ∩

V^{C∗P_{α}} in such a way that

{X_{α} : α < ω_{2}} = [ω_{1}]^{ω_{1}} ∩ V^{C∗P_{ω_{2}}}. (∗)

To construct the poset Q_{α} we need the following induction hypothesize. To formulate it we use two notions. A graph G is strongly nontrivial provided that each uncountable family of pairwise disjoint, finite subsets of V (G) contains four distinct elements, a, b, c, d such that [a, b] ⊂ E(G) and [c, d] ∩ E(G) = ∅. If G is a graph, a set A ⊂ V (G) is called dense in G iff for each pair B and B′ of disjoint finite subsets of V (G) there is α ∈ A such that G(α) ⊃ B and G(α) ∩ B′ = ∅.

Induction Hypothesis .

non-trivial (I) V^{C∗P_{α}} ⊧ “G is strongly non-trivial”, many-dense (II) V^{C∗P_{α}} ⊧ “ ∀X ∈ [ω_{1}]^{ω_{1}} ∃Y ∈ [X]^{<ω} ∀δ < ω_{1} ∃A ∈ [X \ δ]^{ω} A is

dense in G[X \ Y]”,

The preservation of the induction hypothesize (I) and (II) during the iteration will be verified later in lemmas 3.5 and 3.9.

We continue the construction of the poset Q_{α}. Using (II) fix Y_{α} ∈ [X_{α}]^{<ω} and pairwise disjoint countable subsets {D_{ξ} : ξ < ω_{1}} of X_{α}\Y_{α} which are dense in G[X_{α} \ Y_{α}].

Let us recall that for each β < α in the β^{th} step we already constructed an isomorphism f_{β} between G and G[X_{β} \Y_{β}]. For each β < α the set C_{β} = {ν < ω_{1} : f′′_{β}ν ⊂ ν} is clearly club and C_{β} belongs to V^{C∗P_{β}∗Q_{β}} ⊂ V^{C∗P_{α}}. Since P_{α} satisfies c.c.c and |α| < 2^{ω_{1}} = ω_{2} it follows that there is a club set C ⊂ ω_{1} even in V such that |C \ C_{β}| ≤ ω for each β < α.

The club set C = {γ_{ν} : ν < ω_{1}} gives a natural partition A_{α} = {A_{ν}^{α} : ν < ω_{1}} of ω_{1} into countable pieces: let A_{ν}^{α} = [γ_{ν}, γ_{ν+1}) for ν < ω_{1}. We can thin out C to contain only limit ordinals and in this case every A_{ν}^{α} is infinite. Define the map rk_{α} : ω_{1} ⟶ ω_{1} by the formula ξ ∈ A_{rk_{α}(ξ)}^{α}.

If β < α then |C \ C_{β}| ≤ ω and so all but countably many A_{ν}^{α}’s are f_{β}-closed. By shrinking C we can assume every A_{η}^{α} contains some D_{ξ} and so

xdense (i) A_{η}^{α} ∩ (X_{α} \ Y_{α}) is dense in G[X_{α} \ Y_{α}]. Since A_{η}^{α} ∈ V and infinite, it follows

odense (ii) A_{η}^{α} is dense in G.

For η < ω_{1} let O_{η} = [ωη, ωη + ω) and B_{η}^{α} = ⋃{A_{η}^{α} : ν ∈ O_{η}}. Put B_{α} = ⟨B_{η}^{α} : η < ω_{1}⟩.

Given two sets Z and W denote by Bij_{p}(Z, W) the family of bijections between finite subsets Z and W.

If p ∈ Bij_{p}(ω_{1}, X \ Y) a sequence x⃗ = ⟨x_{0}, x_{1}, …, x_{n}, ⟩ of countable ordinals is a p-loop iff n ≥ 1, x_{0} = x_{n} and there is a sequence ⟨k_{0}, …, k_{n−1}⟩ ∈ ^{n}{−1, +1} such that

p-rank (iii) rk_{α}(x_{i+1}) = rk_{α}(p^{k_{i}}(x_{i})) for each i < n, p-triv (iv) there is no i < n such that {k_{i}, k_{i+1}} = {−1, +1}, x_{i+1} = p^{k_{i}}(x_{i})

and x_{i+2} = p^{k_{i+1}}(x_{i+1}). We say that p is loop-free if there is no p-loop. Now we are in the position to define the poset Q_{α}. We put a finite

function p ∈ Iso_{p}(G, G[X_{α} \ Y_{α}]) into Q_{α} iff

p-closed (v) p′′B_{η} ⊂ B_{η} for each η < ω_{1}, p-loop-free (vi) p is loop-free.

As promised, Q_{α} is ordered by the reverse inclusion.

Let us recall that supp p = dom(p) ∪ ran(p) for p ∈ Q_{α}.

We need to show that Q_{α} satisfies c.c.c and a Q_{α}-generic filter gives an isomorphism between G and G[X_{α} \Y_{α}]. First we prove an auxiliary lemma.

lm:disj_un Lemma 3.2. If p, q ∈ Bij_{p}(ω_{1}, ω_{1}), rk_{α}′′ supp p ∩ rk_{α}′′ supp q = ∅ and x⃗ = ⟨x_{0}, …, x_{n}⟩ is a (p ∪ q)-loop, then x⃗ is either a p-loop or a q-loop.

Proof. Assume that x_{0} ∈ supp p. Then x_{0} ∉ supp q, so rk_{α}(x_{1}) = rk_{α}(p^{k_{0}}(x_{0})) for some k_{0} ∈ {−1, +1}. Since p^{k_{0}}(x_{0}) ∈ supp p we have rk_{α}(x_{1}) = rk_{α}(p^{k_{0}}(x_{0})) ∉ rk_{α}′′ supp q and so x_{1} ∉ supp q. Repeating this argument we yield {x_{0}, …, x_{n}} ⊂ supp p \ supp q and so x⃗ is a p-loop.

lm:ccc Lemma 3.3. Q_{α} satisfies c.c.c.

Proof. We work in V^{C∗P_{α}}. Assume that {q_{ξ} : ξ < ω_{1}} ⊂ Q_{α}, c_{ξ} = supp q_{ξ} and r_{ξ} = rk_{α}′′c_{ξ}. Applying standard Δ-system and counting arguments we can find I ∈ [ω_{1}]^{ω_{1}} such that

(1) {c_{ξ} : ξ ∈ I} forms a Δ-system with kernel c,

(2) {r_{ξ} : ξ ∈ I} forms a Δ-system with kernel r,

(3) rk_{α}′′c = r,

(4) rk_{α}′′(c_{ξ} \ c) = r_{ξ} \ r for each ξ ∈ I,

(5) q_{ξ} |` c = q′ for each ξ ∈ I.

Since G is strongly non-trivial in V^{C∗P_{α}} there is {ξ, ζ} ∈ [I]^{2} such that [c_{ξ} \ c, c_{ζ} \ c] ⊂ E(G). We show that q = q_{ξ} ∪ q_{ζ} ∈ Q_{α}. Clearly q ∈ Iso_{p}(G, G[X_{α}\Y_{α}]) and q satisfies (v). Since q = q′∪(q_{ξ}\q′)∪(q_{ζ}\q′) and the sets rk_{α}′′q′, rk_{α}′′(q_{ξ} \ q′) and rk_{α}′′(q_{ζ} \ q′) are pairwise disjoint we have that q satisfies (vi) as well by lemma 3.2.

If G^{Q_{α}} is the Q_{α}-generic filter over V^{C∗P_{α}} let f_{α} = ∪{q : q ∈ G^{Q_{α}}}.

lm:dr-dense Lemma 3.4. V^{C∗P_{α}∗Q_{α}} ⊧ “f_{α} is an isomorphism between G and G[X_{α}\ Y_{α}].”

Proof. We need to prove that dom(f_{α}) = ω_{1} and ran(f_{α}) = X_{α} \ Y_{α} which follows if for each ν ∈ ω_{1} and μ ∈ X \ Y both

D_{ν} = {q ∈ Q_{α} : ν ∈ dom q}

and

R_{μ} = {q ∈ Q_{α} : μ ∈ ran q}

are dense in Q_{α}. Fix q ∈ Q_{α}. Write rk_{α}(ν) = ωη + n. Pick ωη ≤ ζ < ωη + ω such that supp q ∩ A_{ζ}^{α} = ∅. Since A_{ζ}^{α} ∩ (X_{α} \ Y_{α}) is dense in G[X_{α} \ Y_{α}] we can find ν′ ∈ A_{ζ}^{α} ∩ (X_{α} \ Y_{α}) such that {ν′, q(ξ)} ∈ E(G) iff {ν, ξ} ∈ E(G) for each ξ ∈ dom q. Let q′ = q ∪ {⟨ν, ν′⟩}. By the choice of ζ′, rk_{α}(ν′) = ζ ∉ rk_{α}′′(supp q), so this extension of q can not introduce a q′-loop, i.e. q′ ∈ Q_{α}. Thus q′ ∈ D_{ν} and q′ ≤ q which was to be proved. The density of R_{μ} can be verified by a similar argument using the density of A_{ζ}^{α} in G.

The induction step is complete so the theorem is proved provided we can verify the induction hypothesize (I) and (II) in every V^{C∗P_{γ}}. First we deal with (I) because it is fairly easy. Checking (II) is the crux of our proof.

lm:non-trivial Lemma 3.5. The induction hypothesis (I) holds, i.e. G is strongly non-trivial in every V^{C∗P_{α}}.

Proof. First remark that G is clearly strongly non-trivial in V^{C}. By [1, lemma 4.10] we can assume that α = γ + 1 and G is strongly nontrivial in V^{C∗P_{γ}}. Working in V^{C∗P_{α}} assume that q^{∥}— “{ẋ_{ξ} : ξ < ω_{1}} are pairwise disjoint, finite subsets of ω_{1}.” For each ξ < ω_{1} pick a condition q_{ξ} ≤ q and a finite subset x_{ξ} of ω_{1} such that q_{ξ}^{∥}— “ẋ_{ξ} = x_{ξ}”. Since Q_{γ} satisfies c.c.c, we can assume that the sets x_{ξ} are pairwise disjoint.

We can assume that x_{ξ} ⊂ dom q_{ξ} because in lemma 3.4 we showed that the sets D_{ν} are dense in Q_{γ}.

From now on we can argue as in lemma 3.3. Let c_{ξ} = supp q_{ξ} and r_{ξ} = rk_{γ}′′c_{ξ}. We can find I ∈ [ω_{1}]^{ω_{1}} such that {c_{ξ} : ξ ∈} forms a Δ-system with kernel c and {r_{ξ} : ξ ∈ I} forms a Δ-system with kernel r, moreover rk_{γ}′′c = r, rk_{γ}′′(c_{ξ} \ c) = r_{ξ} \ r, q_{ξ} |` c is independent from ξ and x_{ξ} ⊂ c_{ξ} \ c for each ξ ∈ I. Write c′_{ξ} = c_{ξ} \ c, q′_{ξ} = q_{ξ} |` c′_{ξ}, r′_{ξ} = r_{ξ} \ r and q′ = q_{ξ} |` c.

Since G is strongly non-trivial in V^{C∗P_{ξ}} there are ξ_{0}, ξ_{1}, ζ_{0}, ζ_{1} ∈ I such that [c′_{ξ_{0}}, c′_{ζ_{0}}] ⊂ E(G) and [c′_{ξ_{1}}, c′_{ζ_{1}}] ∩ E(G) = ∅ . Then q^{i} = q_{ξ_{i}} ∪ q_{ζ_{i}} ∈ Iso_{p}(G, G[X \ Y]) and q^{i} clearly satisfies (v). Since q^{i} = q′ ∪ q′_{ξ_{i}} ∪ q′_{ζ_{i}} and the sets rk_{γ}′′q′, rk_{γ}′′q′_{ξ_{i}} and rk_{γ}′′q′_{ζ_{i}} are pairwise disjoint we have that q^{i} satisfies (vi) as well by lemma 3.2. Thus

q^{0}^{∥}—[ẋ_{ξ_{0}}, ẋ_{ζ_{0}}] ⊂ E(G)

and

q^{1}^{∥}—[ẋ_{ξ_{1}}, ẋ_{ζ_{1}}] ∩ E(G) = ∅.

Now we start to work on (II).

df:act-freely Definition 3.6. Assume that H is a family of function, dom(h) ∪ ran(h) ⊂ ω_{1} for each h ∈ H. A sequence x⃗ = ⟨x_{0}, x_{1}, …, x_{n}⟩ ∈ nω_{1} is called H-loop if n ≥ 1, x_{0} = x_{n}, and there are sequences ⟨h_{0}, …, h_{n−1}⟩ ∈ ^{n}H and ⟨k_{0}, …, k_{n−1}⟩ ∈ ^{n}{−1, +1} such that

(i) h_{i}^{k_{i}}(x_{i}) = x_{i+1} for each i < n, (ii) there is no i < n−1 such that h_{i} = h_{i+1} and {k_{i}, k_{i+1}} = {−1, +1}. Let Z ⊂ ω_{1}. We say that H acts loop-free on Z if (iii) Z is h-closed for each h ∈ H, (iv) Z does not contain any H-loop.

df:det Definition 3.7. A condition p = ⟨c, q⟩ ∈ C ∗ P_{α} is called determined iff

(i) q is a function, dom(q) ∈ [ω_{1}]^{<ω}, (ii) q(η) is a function for each η ∈ dom(q), (iii) ⋃{supp q(η) : η ∈ dom(q)} ⊂ supp c, (iv) dom(c) = [supp c]^{2}.

The determined conditions are dense in C ∗ P_{α}.

lm:loop-free Lemma 3.8. In V^{C∗P_{α}} for each J ∈ [α]^{<ω} there is μ < ω_{1} such that {f_{ξ} : ξ ∈ J} acts loop-free on ω_{1} \ μ.

Proof. We work in V [G], where G is the C ∗ P_{α}-generic filter over V. The lemma will be proved by induction on max J. Let ζ = max J and J′ = J \ {ζ}. Using the inductive hypothesis fix μ < ω_{1} such that (a) μ = ⋃{B ∈ B_{ζ} : B ∩ μ ≠ ∅},

(b) if A ∈ A_{ζ} and A ⊂ ω_{1} \ μ then A is f_{ξ}-closed for each ξ ∈ J′,

(c) {f_{ξ} : ξ ∈ J′} acts loop-free on ω_{1} \ μ.

Assume on the contrary that ⟨x_{0}, …, x_{n}⟩ ∈ ^{n}(ω_{1} \ μ) is an {f_{ξ} : ξ ∈ J}-loop witnessed by the sequences ⟨g_{i} : i < n⟩ ∈ ^{n}{f_{ξ} : ξ ∈ J} and ⟨k_{i} : i < n⟩ ∈ ^{n}{−1, +1}. Let M = {m < n : g_{m} = f_{ζ}}. By the induction hypothesis M ≠ ∅. Write M = {m_{j} : j < ℓ}, m_{0} < ⋯ < m_{ℓ−1}. Let y_{0} = x_{m_{0}}, y_{1} = x_{m_{1}}, …, y_{ℓ−1} = x_{m_{ℓ−1}} and y_{ℓ} = x_{m_{0}}. Pick

a determined condition ⟨c, q⟩ ∈ G such that y_{j}, f_{ζ}^{k_{m_{j}}} (y_{j}) ∈ dom(q(ζ)) ∩ ran(q(ζ)) for each j < ℓ. We claim that ⟨y_{j} : j ≤ ℓ⟩ is a q(ζ)-loop witnessed by the sequence ⟨k_{m_{j}} : j < ℓ⟩, which contradicts the choice

of Q_{ζ}. Condition (iii) holds because rk_{ζ}(y_{j+1}) = rk_{ζ}(f_{ζ}^{k_{m_{j}}} (y_{j})) by (vi). Assume on the contrary that (iv) fails, i.e, there is j < ℓ such that {k_{m_{j}}, k_{m_{j+1}}} = {−1, +1}, y_{j+1} = f_{ζ}^{k_{m_{j}}} (y_{j}) and y_{j+2} = f_{ζ}^{k_{m_{j+1}}}(y_{j+1}).

Since f_{ζ}^{k_{m_{j}}} (y_{j}) = f_{ζ}^{k_{m_{j}}} (x_{m_{j}}) = x_{m_{j}+1} and y_{j+1} = x_{m_{j+1}}, and so x_{m_{j}+1} = x_{m_{j+1}}, by (c) it follows that m_{j} +1 = m_{j+1}. Similarly, m_{j+1}+1 = m_{j+2}. Thus x_{m_{j}} = y_{j}, x_{m_{j}+1} = y_{j+1} and x_{m_{j}+2} = y_{j+2}. So g_{m_{j}} = g_{m_{j}+1} = f_{ζ} and {k_{m_{j}}, k_{m_{j}+1}} = {−1, +1} which contradicts our assumption that ⟨g_{i} : i < n⟩ and ⟨k_{i} : i < n⟩ satisfied 3.6.(ii).

lm:many-dense Lemma 3.9. The induction hypothesis (II) holds in V^{C∗P_{α}}, i.e. V^{C∗P_{α}} ⊧ “ ∀X ∈ [ω_{1}]^{ω_{1}} ∃Y ∈ [X]^{<ω} ∀δ < ω_{1} ∃A ∈ [X \ δ]^{ω} A is dense in G[X \ Y]”,

Proof. Assume that

1_{C∗P_{α}}^{∥}—X = {ẋ_{ξ} : ξ < ω_{1}} ∈ [ω_{1}]^{ω_{1}}.

Pick determined conditions p_{ξ} = ⟨c_{ξ}, q_{ξ}⟩ ∈ C ∗P_{α} and x_{ξ} ∈ ω_{1} such that p_{ξ}^{∥}— “ẋ_{ξ} = x_{ξ}”. We can assume that x_{ξ} ∈ supp c_{ξ}. Write J_{ξ} = dom q_{ξ} and Z_{ξ} = supp(c_{ξ}).

Now there is K ∈ [ω_{1}]^{ω_{1}} such that the conditions {p_{ξ} : ξ ∈ K} are “pairwise twins”, i.e.

(1) {Z_{ξ} : ξ ∈ K} forms a Δ-system with kernel Z,

(2) {J_{ξ} : ξ ∈ K} forms a Δ-system with kernel J,

(3) max Z < min(Z_{ξ}\Z) < max(Z_{ξ}\Z) < min(Z_{ξ′}\Z) for ξ < ξ′ ∈ K,

(4) |Z_{ξ}| = |Z_{ξ′}| for {ξ, ξ′} ∈ [K]^{2}. Denote by φ_{ξ,ξ′} the natural bijection between Z_{ξ} and Z_{ξ′}.

(5) c_{ξ′}(({φ_{ξ,ξ′}(ν), φ_{ξ,ξ′}(ν′)})) = c_{ξ}({ν, ν′}) for {ν, ν′, } ∈ [Z_{ξ}]^{2} and {ξ, ξ′} ∈ [K]^{2},

(6) q_{ξ′}(η) = {⟨φ_{ξ,ξ′}(ν), φ_{ξ,ξ′}(ν′)⟩ : ⟨ν, ν′⟩ ∈ q_{ξ}(η)} for η ∈ J and {ξ, ξ′} ∈ [K]^{2}.

Since B_{η} is a partition of ω_{1} into countable pieces for η ∈ J, there is a club set C = {γ_{ν} : ν < ω_{1}} ⊂ ω_{1} in V^{C∗P_{α}} such that for each η ∈ J and ν < ω_{1} we have

[γ_{ν}, γ_{ν+1}) = ⋃{B ∈ B_{η} : B ∩ [γ_{ν}, γ_{ν+1}) ≠ ∅}.

Since C ∗ P_{α} is c.c.c we can assume that C ∈ V.

By thinning out K we can assume that if ξ < ξ′ ∈ K then there is γ ∈ C such that max(Z_{ξ} \ Z) < γ < min(Z_{ξ′} \ Z), moreover max Z < min C.

By lemma 3.8 fix μ ∈ C such that δ ≤ μ and 1_{C∗P_{α}}^{∥}— “{f_{η} : η ∈ J} acts loop-free on ω_{1} \ μ”.

If η⃗ = ⟨η_{0}, …, η_{n−1}⟩ ∈ ^{n}J and k⃗ = ⟨k_{0}, …, k_{n−1}⟩ ∈ ^{n}{−1, +1} for some n ∈ ω then let

f_{⟨η⃗,k⃗⟩} = f_{η_{n−1}}^{k_{n−1}} ∘ ⋯ ∘ f_{η_{0}}^{k_{0}}.

If p = ⟨c, q⟩ is determined and J ⊂ dom(q) we define the q-approximation of f_{⟨η⃗,k⃗⟩}, f_{⟨η⃗,k⃗⟩}^{q}, in the natural way:

f_{⟨η⃗,k⃗⟩}^{q} = q(η_{n−1})^{k_{n−1}} ∘ ⋯ ∘ q(η_{0})^{k_{0}}.

We say that f_{⟨η⃗,k⃗⟩} is irreducible if there is no i < n − 1 such that η_{i} = η_{i+1} and {k_{i}, k_{i+1}} = {−1, +1}.

Let ξ ∈ K be arbitrary. An irreducible f_{⟨η⃗,k⃗⟩} is active iff dom f_{⟨η⃗,k⃗⟩}^{q} ∩

(Z_{ξ} \ Z) ≠ ∅, i.e., there is a sequence x⃗ = ⟨x_{0}, …, x_{n−1}⟩ ∈ ^{n}(Z_{ξ} \ Z) such that x_{i+1} = q_{ξ}(η_{i})^{k_{i}}(x_{i}) for i < n. Observe that the definition of activeness above does not depend on the choice ξ because the conditions {⟨c_{ξ}, q_{ξ}⟩ : ξ ∈ K} are pairwise twins.

We say that x⃗ witnesses that f_{⟨η⃗,k⃗⟩} is active.

Let K′ ∈ [K]^{ω}, Ȧ = {⟨p_{ξ}, x_{ξ}⟩ : ξ ∈ K′} and ζ ∈ K \ K′. Let r^{∗} = ⟨c^{∗}, q^{∗}⟩ ≤ p_{ζ} be a determined condition such that for each active f_{⟨η⃗,k⃗⟩} and w ∈ Z the value f_{⟨η⃗,k⃗⟩}^{q^{∗}}(w) is defined. Let

Y = {f_{⟨η⃗,k⃗⟩}^{r^{∗}}(w) : f_{⟨η⃗,k⃗⟩} is active and w ∈ Z}.

Claim . Y is finite.

Proof of the claim. Since {f_{η} : η ∈ J} acts loop-free on Z_{ζ} \ Z, the elements of a witnessing sequence are pairwise different, so there are only finitely many of them and a witnessing sequence works only for one active f_{⟨η⃗,k⃗⟩}. So there is only finitely many active f_{⟨η⃗,k⃗⟩}.

We show that

(•) r^{∗}^{∥}—Ȧ is dense in G[ω_{1} \ Y].

Indeed, assume that r′ ≤ r^{∗}, r′ = ⟨c′, q′⟩ is determined, B ∈ [ω_{1} \ Y ]^{<ω} and b ∈ ^{B}2.

Pick ξ ∈ K such that supp(c′) ∩ supp(c_{ξ}) = Z and dom(q′) ∩ dom(q_{ξ}) = J. To complete the proof of the lemma it is enough to construct a common extension p = ⟨c, q⟩ of r′ = ⟨c′, q′⟩ and p_{ξ} = ⟨c_{ξ}, q_{ξ}⟩ such that c(x_{ξ}, β) = b(β) for each β ∈ B.

Let supp(c) = supp(c′) ∪ supp(c_{ξ}). Put dom q = dom q′ ∪ dom q_{ξ} and let

q(η) = \{ \begin{matrix}q′(η) ∪ q_{ξ}(η) & if η ∈ J, \\ q′(η) & if η ∈ dom q′ \ J, \\ q_{ξ}(η) & if η ∈ dom q_{ξ} \ J. \end{matrix}

Put c^{−} = c′ ∪ c_{ξ}.

We should define c on the set

E = {{a, b} : a ∈ Y_{ξ} \ Y, b ∈ supp c′ \ Y }.

such that every q(η) is a partial isomorphism of G, more precisely, q(η) ∈ Iso_{p}(G^{c}). To do so, observe that if we take

E^{+} = {{a, b} : a ∈ Y_{ξ} \ Y, b ∈ supp c′}.

and for e ∈ E^{+} define a_{e} = e ∩ (Z_{ξ} \ Z) and b_{e} = e ∩ supp c′ then q(η) ∈ Iso_{p}(G^{c}) if and only if (†) below holds:

if e = {a_{e}, b_{e}} ∈ E^{+} then c{a_{e}, b_{e}} = c{q_{ξ}(η)(a_{e}), q′(η)(b_{e})}. (†)

We define an equivalence relation ≡ on E^{+}: e≡e′ iff e = e′ or there is an active pair f_{⟨η⃗,k⃗⟩} such that a_{e′} = f_{⟨η⃗,k⃗⟩}^{q_{ξ}}(a_{e}) and b_{e′} = f_{⟨η⃗,k⃗⟩}^{q′}(b_{e}).

cl:1 Claim 3.9.1. If e ≡ e′ and a_{e} = a_{e′} then e = e′.

Proof of the claim 3.9.1. Assume e≡e′ and b_{e} ≠ b_{e′}. Then there is an active f_{⟨η⃗,k⃗⟩} such that a_{e′} = f_{⟨η⃗,k⃗⟩}^{q_{ξ}}(a_{e}) and b_{e′} = f_{⟨η⃗,k⃗⟩}^{q′}(b_{e}). Since 1^{∥}—

“{f_{η} : η ∈ J} acts freely on ω_{1} \ μ” it follows that a_{e} ≠ f_{⟨η⃗,k⃗⟩}^{q′}(a_{e}) and

so a_{e} ≠ a_{e′}.

cl:2 Claim 3.9.2. If e, e′ ∈ E^{+} ∩ dom(c^{−}) and e ≡ e′ then c^{−}(e) = c^{−}(e′).

Proof of the claim 3.9.2. Fix an active f_{⟨η⃗,k⃗⟩} such that a_{e′} = f_{⟨η⃗,k⃗⟩}^{q_{ξ}}(a_{e})

and b_{e′} = f_{⟨η⃗,k⃗⟩}^{q′}(b_{e}). Since e, e′ ∈ E^{+} ∩ dom(c^{−}) it follows that e, e′ ∈

dom(c_{ξ}) and so a_{e}, a_{e′} ∈ Z. Thus b_{e′} = f_{⟨η⃗,k⃗⟩}^{q_{ξ}}(b_{e}). But f_{⟨η⃗,k⃗⟩}^{q_{ξ}} ∈ Iso_{p}(G^{c_{ξ}})

for ⟨c_{ξ}, q_{ξ}⟩ ∈ C ∗ P_{α} so c_{ξ}(e) = c_{ξ}(e′).

cl:3 Claim 3.9.3. If e ∈ E^{+} ∩ dom(c^{−}) and e ≡ e′ then b_{e′} ∈ Y.

Proof of the claim 3.9.3. Since e ∈ E^{+} ∩ dom(c^{−}) we have b_{e} ∈ Z. Fix an active f_{⟨η⃗,k⃗⟩} such that a_{e′} = f_{⟨η⃗,k⃗⟩}^{q_{ξ}}(a_{e}) and b_{e′} = f_{⟨η⃗,k⃗⟩}^{q′}(b_{e}). Since

f_{⟨η⃗,k⃗⟩} is active it follows that f_{⟨η⃗,k⃗⟩}^{q^{∗}}(b_{e}) is defined and f_{⟨η⃗,k⃗⟩}^{q^{∗}}(b_{e}) ∈ Y.

But f_{⟨η⃗,k⃗⟩}^{q′}(b_{e}) = f_{⟨η⃗,k⃗⟩}^{q^{∗}}(b_{e}) so b_{e′} ∈ Y which was to be proved.

By claims 3.9.1–3.9.3 we can find a condition c ∈ C with supp c = supp c′ ∪ supp c_{ξ} and dom c = [supp c]^{2} such that

(a) c ⊃ c′ ∪ c_{ξ},

(b) c(e) = c(e′) whenever e≡e′,

(c) c(x_{ξ}, β) = b(β) for β ∈ B. Then (†) holds and as we have seen above, ⟨c, q⟩ ∈ C ∗ P_{α} and

⟨c, q⟩^{∥}—(∀β ∈ B) {x_{ξ}, β} ∈ E(G) iff b(β) = 1.

Thus (•) holds. Hence lemma 3.9 is proved.

So we have shown that (II) is preserved during the inductive construction, which was the last step to prove theorem 3.1

References

HNS [1] A. Hajnal, Zs. Nagy, L. Soukup, On the number of non-isomorphic subgraphs of certain graphs without large cliques and independent subsets, “A Tribute to Paul Erdős ”, e.d. A Baker, B. Bollobás, A. Hajnal, Cambridge University Press, 1990, p. 223-248

J [2] T. Jech, Set Theory, Academic Press. New York, 1978. KN [3] H. A. Kierstead, P. J. Nyikos, Hypergraphs with Finitely many Isomorphism

Subtypes, Trans. Amer. Math. Soc. 312 (1989) 699-718.

ShSo [4] S. Shelah, L. Soukup, On the number of non-isomorphic subgraphs , Israel J. Math, 86(1994) no 1-3, 349-371.

Mathematical Institute of the Hungarian Academy of Sciences,, Budapest, V. Reáltanoda u. 13-55, Hungary

  E-mail address: soukup@math-inst.hu