> k−HOMOGENEOUS INFINITE GRAPHS OVE AHLMAN 6 1 0 2 Abstract. Inthisarticlewegiveanexplicitclassificationforthecount- r ablyinfinitegraphsG whichare,forsomek,≥k-homogeneous. Itturns a out that a ≥k−homogeneous graph M is non-homogeneous if and only M if it is either not 1−homogeneous or not 2−homogeneous, both cases which may be classified using ramsey theory. 8 ] O 1. introduction C . AgraphG iscalledk−homogeneousifforeachinducedsubgraphA ⊆ G h such that |A| = k and embedding f : A → G, f may be extended into t a an automorphism of G. If G is t−homogeneous for each t ≥ k (t ≤ k) m then G is called ≥k−homogeneous (≤k−homogeneous). A graph which [ is both ≥k−homogeneous and ≤k−homogeneous is plainly called homoge- 2 neous. Lachlan and Woodrow [9] classified the countably infinite homoge- v neous graphs. Since then, the study of homogeneous structures have been 7 continued in many different ways. When it comes to countably infinite ho- 0 3 mogeneous structures Cherlin [3] classified all such digraphs and Lachlan 7 [10] classified all such tournaments. Even more kinds of infinite homo- 0 geneous structures have been classified, however few results about infinite . 1 k−homogeneousstructureswhicharenothomogeneousseemtoexist. When 0 itcomestofinitestructuresGardiner[6]andindependentlyGolfandandKlin 6 1 [8]classifiedallhomogeneousfinitegraphs. Cameron[2]extendedthistothe : k−homogeneouscontextandshowedthatany≤5−homogeneousgraphisho- v i mogeneous. Thus classifying the finite k−homogeneous graphs comes down X to the cases which are not t−homogeneous for some t ≤ 5. Among others, r a Chia and Kok [5] took on this task and characterized finite k−homogeneous graphs with a given number of isolated vertices and nontrivial components. In general though no known characterization of the finite k−homogeneous, ≥k−homogeneous or ≤k−homogeneous graphs exist. In the present article howeverwedomakeprogressinthesubjectwhenitcomestoinfinitegraphs, and provide a full classification of all ≥k−homogeneous infinite graphs. For each t ∈ Z+ define the graph G as having universe G = Z×{1,...,t} t t and edges E = {{(a,i),(b,j)} : a (cid:54)= b}. If t ≥ 2 let H be the graph with t,1 2010 Mathematics Subject Classification. 05C75, 05C63, 03C50. Key words and phrases. >k-homogeneous, classification, countably infinite graph. 1 2 OVEAHLMAN ... ... ... ... ... ... ... ... ... ... ... ... Figure 2. The Figure 1. The graph G ∪˙K 2 3 graph H 2,1 universe H = Z×{1,...,2t} and edges t,1 E = {{(a,i),(b,j)} : i,j ≤ t or i,j > t, and a (cid:54)= b}. t,1 Let H have the same universe as H but with edge set t,2 t,1 E = E ∪{{(a,i),(b,j)} : i ≤ t,j > t and a = b}. t,2 t,1 Lastly define the graph H as having universe Z × {1,2} and edge set 1,2 E = {{(a,i),(b,j)} : i = j or a = b but i (cid:54)= j}. Theorem 1.1. Let k ∈ N. Then M is a ≥k−homogeneous graph if and only if exactly one of the following hold. (i) M is a homogeneous graph. (ii) M is not 1−homogeneous and for some finite homogeneous graph H and some t we have that M ∼= G ∪˙H or M ∼= (G ∪˙H)c. t t (iii) M is 1−homogeneous but not 2−homogeneous and for some t we have that M ∼= H , M ∼= H , M ∼= Hc or M ∼= Hc . t,1 t,2 t,1 t,2 Asthefinitehomogeneousgraphsareclassifiedaseitherthe3×3rookgraph, the5−cycle, adisjointunionofcompletegraphsorthecomplementofoneof the previous graphs, case (ii) is complete. We prove (ii) in Section 2 Lemma 2.1, (iii) in Section 3 Lemma 3.1 and lastly in Section 4 Lemma 4.1 we show that any ≥k−homogeneous graph which does not fit into (ii) or (iii) has to be homogeneous, in other words, (i) is proven. A graph G is homogenizable if there exists a homogeneous structure M with a finite amount of extra relational symbols in its signature compared to G such the automorphism groups of M and G are the same and if we remove all extra relations from M, we get G. For a more detailed definition of homogenizable structures and explicit examples see [1, 11]. From the proof of Theorem 1.1 we can draw the following two corollaries which relate to being homogenizable. >k−HOMOGENEOUS INFINITE GRAPHS 3 Corollary 1.2. If, for some k, M is a countably infinite ≥k−homogeneous graph which is not 1−homogeneous then M is homogenizable by only adding a single unary relation symbol. Corollary 1.3. If, for some k, M is a countably infinite ≥k−homogeneous graph which is 1−homogeneous but not 2−homogeneous then M is homog- enizeable by adding only a single binary relation symbol and one of the fol- lowing holds: • k = 5 and M ∼= H or M ∼= Hc . 1,2 1,2 • k = 2n+1 > 3 and M ∼= H or M ∼= Hc . n,1 n,1 • k = 4n+1 > 5 and M ∼= H or M ∼= Hc . n,2 n,2 Note that an overlap between cases is to be expected. Corollary 1.2 does not have an explicit classification of M depending on k, such as Corollary 1.3, since M ∼= G ∪˙H or M ∼= (G ∪˙H)c where both t and H affect for which t t k that M is ≥k−homogeneous. It is clear in Corollary 1.3 that we may add a unary relation symbol to make the graph homogeneous. This however does not follow the definition of being homogenizable since adding a unary relation symbol changes the automorphism group. In the terminology of Cherlin [4] we have proven that a ≥k−homogeneous graph has relational complexity at most 2. Notation and terminology. For each t ∈ Z+, K is the complete graph t on t vertices and K is the countably infinite complete graph. Whenever we ∞ talk about subgraphs H ⊆ G we mean induced subgraph in the sense that for a,b ∈ H we have that aEGb if and only if aEHb. An embedding of graphs f : G → H is an injective function such that for each a,b ∈ G we have aEGb if and only if f(a)EHf(b). If we write K ⊆ G or K ⊆ G it means that for t ∞ some subgraph H of G, H is isomorphic to K or K respectively. If G is t ∞ a graph with a ,...,a ∈ G then K (a ,...,a ) is a complete subgraph of G 1 r t 1 r containing t vertices, which includes a ,...,a . For t ∈ Z+, a t−orbit of G is 1 r an orbit of t−tuples which arise when the automorphism group of G acts on Gt. One of our main tools in the proofs is Ramsey’s famous theorem about the existence of infinite complete or infinite independent subgraphs which now a days is common practice and may be found in for instance [7]. Fact 1.4 (Ramsey’s Theorem). If G is an infinite graph then K ⊆ G or ∞ Kc ⊆ G. ∞ 2. Graphs which are not 1−homogeneous Lemma 2.1. For some k ∈ N, M is a ≥k−homogeneous graph which is not 1−homogeneous if and only if there exists t ∈ N and a finite homogeneous graph H such that M ∼= G ∪˙H or M ∼= (G ∪˙H)c. t t Proof. Lemma2.8provesthatifMis≥k−homogeneousandK ⊆ Mthen ∞ M ∼= G ∪˙H for some t ∈ N and homogeneous finite graph H. It follows that, t using Ramsey’s theorem, if K (cid:54)⊆ M then Kc ⊆ M in which case it follows ∞ ∞ 4 OVEAHLMAN similarly that M ∼= (G ∪˙H)c. t In order to prove the second direction assume that M ∼= G ∪˙H and notice t that both G and H are homogeneous graphs and as subgraphs of M they t constitute distinct 1−orbits which are not connected to each other. Let G(cid:48) ⊆ M be such that |G(cid:48)| = k = 3max(|H|,t). There are at least 2t vertices in G(cid:48) which belong to G , thus there exists a vertex a ∈ G(cid:48) which is adjacent t to at least |H| vertices in M. Furthermore if b ∈ G then b is adjacent t either to a or an element in G(cid:48) which a is adjacent to. Thus any embedding f : G(cid:48) → M has to map G(cid:48)∩G into G and G(cid:48)∩H into H. As H and G are t t t both homogeneous this means that f can be extended to an automorphism of M, thus M is ≥k−homogeneous. (cid:3) In the rest of this section we assume that M is ≥k−homogeneous but not 1−homogeneous, thus M has more than one 1−orbit. Due to Ramsey’s theorem K or Kc is embeddable in M. We will assume that K is em- ∞ ∞ ∞ beddable in M. The reader may notice that all the reasoning in this section may be done in the same way if Kc would be embeddable by switching all ∞ references of edges and non-edges, thus producing a result for the comple- ment. Lemma 2.2. There are exactly two 1−orbits in M and one of them is finite. Proof. Since M is ≥k−homogeneous, all elements which are in K ⊆ M ∞ have to be in the same 1−orbit, call it p. Assume that a,b ∈/ p and note that a and b are adjacent to at most k−1 elements in K ⊆ M. Thus we may 3k find G ⊆ K ⊆ M such that |G| = k and no element in G is adjacent to a or 3k b. Let f : G∪{a} → G∪{b} be the embedding which maps G to G and a to b. Since M is ≥k−homogeneous f may be extended to an automorphism, thus a and b belong to the same orbit. The orbit p has to be infinite since all elements in K ⊆ M belong to p. ∞ Assumethatthesecondorbit, callitq, isalsoinfinite. ByRamsey’stheorem either K or Kc is embeddable in q, however K is impossible since M ∞ ∞ ∞ is ≥k−homogeneous and the orbits p and q are distinct. Each element in Kc ⊆ q ⊆ Misadjacenttoatmostk−1elementsinK ⊆ p. Howeverthen ∞ k there has to be a ∈ K ⊆ p and G ⊆ Kc ⊆ q such that |G| = k and a is not k ∞ adjacenttoanyelementinG. Butthenanyembeddingf : G∪{a} → G∪{a} which does not fixate a will be extendable to an automorphism, by the ≥k−homogeneity of M. Thus a ∈ q, which contradicts that a ∈ p. (cid:3) We will keep notation from the previous Lemma and let p be the infinite 1−orbit and let q be the finite 1−orbit in M. Lemma 2.3. If a ∈ p and b ∈ q then a is not adjacent to b. Proof. If some element in p is adjacent to some element in q then for each a ∈ p there exists some b ∈ q such that a is adjacent to b . As p is infinite 0 0 0 0 and q is finite, there has to exist b ∈ q such that b is adjacent to an infinite amount of vertices in K ⊆ M. However, if G ⊆ K ⊆ M with |G| = k ∞ ∞ >k−HOMOGENEOUS INFINITE GRAPHS 5 such that all vertices in G are adjacent to b then there is an embedding f : G∪{b} → G∪{b} which does not fixate b. Since M is ≥k−homogeneous it is possible to extend f to an automorphism of M. Thus b ∈ p which is a contradiction. (cid:3) As Lemma 2.3 prove that p and q are not connected to each other, the next lemma shows that each element in p is non-adjacent to at most k −1 elements in p. Lemma 2.4. If a ∈ p then there are at most k+|q|−1 elements in M which a is not adjacent to. Proof. Assume a ∈ p is not adjacent to any elements in some G(cid:48) ⊆ M such that |G(cid:48)| = k +|q| and let G = G(cid:48) ∩p. By Lemma 2.3 no element in G is adjacent to any element in q. Assume b ∈ q. The function f : G ∪{a} → G∪{b} mapping G to G and a to b is thus an embedding. Since |G| ≥ k it is possible, by ≥k−homogeneity, to extend f into an automorphism. It follows that a ∈ q which is a contradiction. (cid:3) K (a) is any subgraph G of M which is isomorphic to K and contain a. ∞ ∞ Thus the following lemma proves that b is adjacent to all elements (except a) in all K ⊆ M which contain a. ∞ Lemma 2.5. If a,b ∈ p are such that a is not adjacent to b then b is adjacent to each element in K (a)−{a}. ∞ Proof. Assume that each element in p is non-adjacent to exactly t other elements in p. Assume in search for a contradiction that d ∈ K (a)−{a} is ∞ not adjacent to b. Each pair of distinct elements from K (a) belong to the ∞ same 2−orbit. Thus for any distinct α,β ∈ K (a) there exists γ ∈ p such ∞ that α and β are both not adjacent to γ. This however implies either that a would be non-adjacent to more than t different elements or that there would exist some element c ∈ p which is non-adjacent to more than t elements in K (a). Both of these conclusions lead to a contradiction since we have ∞ assumed each element in p to be non-adjacent to exactly t other elements in p. (cid:3) Lemma 2.6. If a,b,c ∈ p are such that a is not adjacent to b and a is not adjacent c, then b is not adjacent to c. Proof. Assume that b is adjacent to c. Lemma 2.5 implies that both b and c are adjacent to each element in K (a)−{a}. Thus (K (a)∪{b,c})−{a} ∞ ∞ is a complete graph, where both b and c are non-adjacent to a. As b is not adjacent to a and c ∈ K (b,c), Lemma 2.5 implies that c is adjacent to a ∞ which is a contradiction. (cid:3) Lemma 2.7. If a,b ∈ p and a is adjacent to b then there exists G ⊆ M such ∼ that a,b ∈ G and G = K . ∞ 6 OVEAHLMAN Proof. If a is adjacent to an infinite amount of elements in some subgraph ∼ G ⊆ M such that G = K and b ∈ G, then the lemma holds. Assume, in ∞ search for a contradiction, that there exist elements c,d ∈ K (b) such that ∞ a is not adjacent to both c and d. Lemma 2.6 then implies that c is not adjacent to d, which is a contradiction. (cid:3) We now summarize all our knowledge about p and q into the following lemma which proves the second part of this section’s main Lemma 2.1. Lemma 2.8. For some t ∈ Z+, p ∼= G and M ∼= G ∪˙H for some homoge- t t neous finite graph H. Proof. Assumethateachelementa ∈ pisnon-adjacenttotelementsb ,...,b 1 t ∈ p. By Lemma 2.6 these t elements always form a Kc. If c ∈ p is adjacent t to b , for some i ∈ {1,...,t}, then Lemma 2.5 and Lemma 2.7 implies that i ∼ c is adjacent to all of b ,...,b . It is thus clear that p = G . 1 t t IfwechooseG ⊆ Msuch that|G∩p| > k thenanyembeddingf : G → M has to be possible to extend into an automorphism. Thus f has to preserve the orbits. However, as q and p have no vertices which are adjacent to each other any embedding g : q → q is possible to extend into an automorphism of q, hence q is a finite homogeneous graph. We conclude that M ∼= G ∪˙H t for some finite homogeneous graph H. (cid:3) 3. Graphs which are 1−homogeneous but not 2−homogeneous Lemma 3.1. A countably infinite graph M is ≥k−homogeneous, for some k ∈ N, 1−homogeneous but not 2−homogeneous if and only if there exists t such that M ∼= H , M ∼= H , M ∼= Hc or M ∼= Hc . t,1 t,2 t,1 t,2 Proof. We prove that the suggested graphs are actually ≥k−homogeneous, forsomek,andtheotherdirectionisdoneinLemma3.12. Wefirstnotethat if M = H or M = H then there are two parts in M, each of which is t,1 t,2 ∼ isomorphic to G for some r. If M = H and G ⊆ M such that |G| ≥ 2t+1 r t,1 there has to be at least one edge between some elements a,b ∈ G. Thus if f : G → M is an embedding, each vertex adjacent to a or b will then be mapped to one of the G parts of M and each vertex not adjacent a nor r b, will be mapped the other G part. As no edges exist between the two r parts and each part is a homogeneous graph f may be extended into an automorphism. ∼ If M = H and G ⊆ M with |G| ≥ 4t + 1 then there exist vertices t,2 a,b,c ∈ G which are adjacent to each other. If f : G → M then a,b and c needs to be mapped to the same part. An element d ∈ G is mapped to the same part as a,b and c if and only if it is adjacent to two of these vertices. As edges between parts are preserved by f and each part is homogeneous, f may be extended into an automorphism. If M ∼= Hc or M ∼= Hc then the reasoning is equivalent. (cid:3) t,1 t,2 >k−HOMOGENEOUS INFINITE GRAPHS 7 In order to prove the second direction of Lemma 3.1, we will assume throughout the rest of this section that M is ≥k−homogeneous, 1−homoge- neous but not 2−homogeneous i.e. there are more than three 2−orbits but only a single 1−orbit. Due to Ramsey’s theorem M has to contain either K orKc . WewillassumethatMcontainsK andthereadermaynotice ∞ ∞ ∞ thatallthereasoninginthissectionmaybedoneinthesamewayforKc by ∞ switching all references to edges and non-edges. Since there is only a single 1−orbit, writing K (a) always makes sense for any vertex a ∈ M, while ∞ writing K (a,b) needs to be motivated in order to show existence. ∞ Lemma 3.2. There are at most two 2−orbits containing tuples of adjacent elements in M and there are at most two 2−orbits containing tuples of dis- tinct non-adjacent elements in M. Proof. Assume (a,b ), (a,b ) and (a,b ) are three different 2−orbits such 1 2 3 that a is adjacent to b ,b and b . We may assume that a is the first co- 1 2 3 ordinate of all three parts without loss of generality, since we only have a single 1−orbit in M. One of the 2−orbits may be assumed to be a part of a K , say (a,b ). Since M is ≥k−homogeneous this property is unique for ∞ 1 the orbit of (a,b ). But then neither b nor b may be adjacent to more than 1 2 3 k−1 of the elements in K (a,b ). Thus we are able to find G ⊆ K (a,b ) 3k 1 3k 1 such that a ∈ G, |G| ≥ k and nothing in G, except a, is adjacent to b or b . 2 3 The function f : G ∪{b } → G ∪{b } mapping G and b to G and b is an 1 3 2 3 embedding, and hence the ≥k−homogenity implies that (a,b ) and (a,b ) 2 3 are of the same orbit, contradicting the assumption. For the second part of the lemma, assume (c,d ), (c,d ) and (c,d ) are 1 2 3 different 2−orbits such that c is non-adjacent to all of d ,d and d . Since 1 2 3 the orbits are different the ≥k−homogenity implies that d is adjacent to 1 at least k of the vertices in K (c) if and only if d is adjacent to at most 2k 2 k−1 vertices in K (c). However, d has to be adjacent or non-adjacent to 2k 3 at least k vertices in K (c) and hence the orbit of (c,d ) can’t be distinct 2k 3 from the two other orbits by the ≥k−homogenity of M. (cid:3) The previous lemma implies that we may assume there are at most five 2−orbits in M, out of which one is the orbit containing identical element 2−tuples (x,x). Call the 2−orbits where elements have an edge between them, q and q and assume that q is the orbit of pairs of elements in K . 1 2 1 ∞ Itfollowsthat(a,b) ∈ q ifaisadjacenttolessthank−1elementsinK (b) 2 ∞ and a is adjacent to b. Lemma 3.3. For each a ∈ M, there are only a finite, possibly zero, amount of elements b ∈ M such that (a,b) ∈ q . 2 Proof. Let A ⊆ M be the subgraph containing all elements b such that a (a,b) ∈ q and assume in search for a contradiction that A is infinite. By 2 a Ramsey’s theorem either K ⊆ A or Kc ⊆ A . If K ⊆ A then, since a is k a k a k a adjacent to each element in A , for any b ∈ K ⊆ A , (a,b) ∈ q which is a a k a 1 contradiction against that (a,b) ∈ q . 2 8 OVEAHLMAN OntheotherhandassumethatKc ⊆ A andb ∈ Kc. EachelementinA k a k a is adjacent to less than k−1 elements in K (a), thus there exists a vertex ∞ c ∈ K (a) such that none of the elements in Kc ⊆ A is adjacent to c. The ∞ k a function f : Kc∪{a} → (Kc−{b})∪{a,c} mapping (Kc−{b})∪{a} back k k k to it self pointwise and b to c is then an embedding. Thus ≥k−homogenity imply that (a,b) ∈ q , which is a contradiction. (cid:3) 1 Call the 2−orbits of tuples of elements which have no edge between them p and p . Assume p is the orbit of pairs (a,b) such that b is adjacent to 1 2 1 at most k−1 of the elements in K (a). We note that p has to exist, since ∞ 1 elseq can’texist, whichwouldimplythatMhasatmostthree2−orbits. It 2 follows,usingthe≥k−homogenity,thateachelementbwhichisnon-adjacent to at least k−1 elements in K (a) is such that (a,b) ∈ p . Thus the orbit ∞ 1 p contains all pairs (a,b) such that a and b are non-adjacent yet b is non- 2 adjacent to less than k −1 elements in K (a). It follows quickly from the ∞ definition, and the ≥k−homogenity, that the four orbits p ,p ,q and q are 1 2 1 2 symmetric in the sence that (a,b) ∈ r implies (b,a) ∈ r. Lemma 3.4. Let a,b,c ∈ M. If (a,b) ∈ q ,(a,c) ∈ p and b is not adjacent 1 1 to c then (b,c) ∈ p . 1 Proof. Since (a,c) ∈ p , c is adjacent to at most k−1 elements in K (a,b), 1 ∞ thus (b,c) ∈ p . (cid:3) 1 We are now ready to prove that, similarly to q , the orbit p is finite if we 2 2 fixate one component. Lemma 3.5. For each a ∈ M there are only a finite, possibly zero, amount of elements b ∈ M such that (a,b) ∈ p . 2 Proof. Assume c is such that (a,c) ∈ p , let L be the set of all elements 1 b ∈ M such that (a,b) ∈ p and assume that L is infinite. By Ramsey’s 2 theorem, we either have K ⊆ L or Kc ⊆ L. ∞ ∞ If K ⊆ L then all these elements are non-adjacent to a but then the ∞ definition of p implies that (a,b(cid:48)) ∈ p for each b(cid:48) ∈ K ⊆ L. This is a 1 1 ∞ contradiction against (a,b(cid:48)) ∈ p . 2 Assume instead that Kc ⊆ L and let G ⊆ Kc ⊆ L be such that all ∞ ∞ elementsinG arenon-adjacenttoc. If|G| ≥ k−2thenanyinjectivefunction f : G ∪{a} → G ∪{a,c} is an embedding, thus ≥k−homogenity imply that (a,c) is in the same orbit as (a,d) for any d ∈ G. This is a contradiction, since (a,d) ∈ p and (a,c) ∈ p , thus |G| ≤ k−3. Together with (a,b) ∈ p 2 1 2 thisimpliesthatthereisanelemente ∈ K (a)andH ⊆ Kc ⊆ L, suchthat ∞ ∞ |H| = 2k andbothcandeareadjacenttoallelementsinH. Assumewithout loss of generality that b ∈ H. There are embeddings g : H∪{c} → H∪{a,e} which map (b,c) to (a,e). This together with ≥k−homogenity imply that (b,c) ∈ q . Lemma 3.4 together with (b,c) ∈ q , (a,c) ∈ p and (a,b) ∈ p 1 1 1 2 implies that (a,b) ∈ p which is a contradiction. (cid:3) 1 >k−HOMOGENEOUS INFINITE GRAPHS 9 The next lemma shows that the orbits q and p , in some sense, are closed 1 2 and together form a tight part of the graph M. This is a vital property which will be used many times in order to handle q and p in the rest of 1 2 the section. Lemma 3.6. Leta,b,c,d ∈ Msuchthatc (cid:54)= d,(a,b) ∈ q and(a,c),(a,d) ∈ 1 p . Then (b,c) ∈ q and (c,d) ∈ p . 2 1 2 Proof. If b is not adjacent to c then, for every a(cid:48) ∈ K (a), since (a(cid:48),a) ∈ ∞ q , there has to exist an element c(cid:48) such that (a,c(cid:48)),(a(cid:48),c(cid:48)) ∈ p . But 1 2 this contradicts Lemma 3.5, since each element c such (a,c ) ∈ p is non- 0 0 2 adjacent to at most k−1 elements in K (a). Thus we conclude that only ∞ a in K (a) can be non-adjacent to c, hence b is adjacent to c and more ∞ specifically (b,c) ∈ q . 1 Assume(c,d) ∈/ p andnotethat(a,c),(a,d) ∈ p impliesthatcanddare 2 2 non-adjacent to a finite amount of elements in K (a). Thus c is adjacent ∞ to an infinite amount of elements in K (b) and hence we conclude that ∞ (c,d) ∈ q . We previousply proved in this lemma though that (c,d) ∈ q 1 1 and (c,a) ∈ p implies that (d,a) ∈ q which is a contradiction against 2 1 (a,d) ∈ p . (cid:3) 2 Itismuchhardertogetagripoftheorbitsq andp . Thisisaconsequence 2 1 of that we assumed K ⊆ M and thus having neighbors which are also ∞ adjacent to some element is easy to handle. The rest of the section will be dedicated to reasoning out how these orbits work in M. Lemma 3.7. Foreacha,b ∈ Mif(a,b) ∈ q theneachelementc ∈ K (a)− 2 ∞ {a} will be such that (b,c) ∈ p . 1 Proof. Assume c is adjacent to b. For every element c ∈ K (a), (c ,a) 0 ∞ 0 is in the same 2−orbit as (c,a) thus there exists an element d such that 0 (a,d ),(c ,d ) ∈ q . This implies either that there is an infinite amount of 0 0 0 2 elements d(cid:48) such that (a,d(cid:48)) ∈ q or that there is an element d(cid:48)(cid:48) such that 2 (d(cid:48)(cid:48),c ) ∈ q for an infinite amount of elements c ∈ K (a). However both 0 2 0 ∞ of these conclusions are contradictions against Lemma 3.3. Thus c is not adjacent to b. By the definition of q , there exists some G ⊆ K (a) such 2 ∞ that |G| ≥ k and each element in G is non-adjacent to b, thus (b,c) ∈ p . (cid:3) 1 In the upcoming two lemmas we will show that the orbit q and the orbit 2 p are very closely linked, and in fact most cases where q exist, also p has 2 2 2 to exist. Lemma 3.8. If a,b ,b ∈ M, b (cid:54)= b and (a,b ),(a,b ) ∈ q then (b ,b ) ∈ 1 2 1 2 1 2 2 1 2 p . 2 Proof. By Lemma 3.7 if d ∈ K (b ) then d can at most be adjacent to k−1 ∞ 1 elements in K (a). If (b ,b ) ∈ q then b ∈ K (b ) which together with ∞ 1 2 1 1 ∞ 2 Lemma 3.7 implies that (a,b ) ∈ p which is a contradiction. 1 1 Assume instead that (b ,b ) ∈ q . Choose G ⊆ K (a) and d ∈ K (b ) 1 2 2 ∞ ∞ 1 10 OVEAHLMAN such that |G| = k and all elements in G are non-adjacent to b ,b and d. 1 2 The function f : G ∪{b ,d} → G ∪{b ,b } mapping G to G and (b ,d) to 1 1 2 1 (b ,b ) is then an embedding, thus ≥k−homogenity implies that (b ,b ) and 1 2 1 2 (b ,d) belong to the same orbit which is a contradiction as (b ,d) ∈ q . We 1 1 1 conclude that b must be nonadjacent to b . 1 2 Assume (b ,b ) ∈ p and let c ∈ K (a). It is then possible to find 1 2 1 ∞ G ⊆ K (b ) such that |G| = k and all elements in G are non-adjacent to a,c ∞ 1 and b . If f : G ∪{a,c} → G ∪{a,b } maps G to G and (a,c) to (a,b ) then 2 2 2 the ≥k−homogenity implies that (a,c) ∈ q , which is a contradiction. (cid:3) 2 Lemma 3.9. Let a,b,c ∈ M. If (a,b) ∈ q and (b,c) ∈ p then (a,c) ∈ q . 2 2 2 Proof. By Lemma 3.6 we know that (a,c) ∈/ q and (a,c) ∈/ p . Assume, in 1 2 search for a contradiction, that (a,c) ∈ p . Let d ∈ K (b)−{b} and note by 1 ∞ Lemma3.7that(a,d) ∈ p . Since(a,d)and(a,c)areinthesameorbit,there 1 has to exist an element e ∈ M, corresponding to what b is to (a,d), such that(e,c) ∈ q and(e,a) ∈ q . Lemma3.8nowimpliesthat(e,b) ∈ p which 1 2 2 in turn together with Lemma 3.6 implies that (e,c) ∈ p . But (e,c) ∈ q , 2 1 hence this is a contradiction and we can conclude that (a,c) ∈ q . (cid:3) 2 Lastly we figure out how the orbit p behaves. This is the hardest orbit 1 to handle, as it induces so little information about edges. Lemma 3.10. Let a,b,c ∈ M. If (a,b) ∈ p and (a,c) ∈ p then (b,c) ∈ p . 1 2 1 Proof. Lemma 3.6 implies that (b,c) ∈/ q and (b,c) ∈/ p , and Lemma 3.9 1 2 implies that (b,c) ∈/ q , thus we conclude that (b,c) ∈ p . (cid:3) 2 1 Lemma 3.11. Let a,b,c ∈ M with b (cid:54)= c. If (a,b),(a,c) ∈ p then (b,c) ∈ q 1 1 or (b,c) ∈ p . 2 Proof. Assume (b,c) ∈ q and let G ⊆ K (a) be such that |G| = k and 2 ∞ both b and c are non-adjacent to each element in G. By the definition of p 1 and Lemma 3.7 there exists d ∈ K (b) such that d is non-adjacent to each ∞ element in G and to c. The function f : G ∪{b,d} → G ∪{b,c} mapping G ∪ {b} pointwise to G ∪ {b} and d to c is then an embedding, which by the ≥k−homogenity may be extended into an automorphism. This is a contradiction since (b,c) ∈ q but (b,d) ∈ q . 2 1 Assume for the rest of this proof that (b,c) ∈ p . In order to reach a 1 contradiction in this case we will also need to make assumptions on which of the orbits q and p exists. Assume that p exist, let d be such that 2 2 2 (a,d) ∈ p . Lemma 3.10 implies that (b,d) ∈ p , thus d is adjacent to at 2 1 most k − 1 elements in K (b). We may then find G ⊆ K (b) such that ∞ ∞ |G| = k and all elements in G are non-adjacent to a,c and d. Thus the function f : G∪{a,d} → G∪{a,c} mapping G∪{a} to itself pointwise and d to c is an embedding. Since M is ≥k−homogeneous f may be extended into an automorphism which implies that (a,d) ∈ p which is a contradiction. 1 Assume q exists and that d is such that (a,d) ∈ q . If both b and c 2 2 are non-adjacent to less than k elements in K (d) then there is an infinite ∞