ARS MATHEMATICA CONTEMPORANEA ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 16 (2019) 331-348 https://doi.org/10.26493/1855-3974.1427.75c (Also available at http://amc-journal.eu) Intrinsic linking with linking numbers of specified divisibility Christopher Tuffley School of Fundamental Sciences, Massey University, Private Bag 11 222, Palmerston North 4442, New Zealand Received 20 June 2017, accepted 29 November 2018, published online 16 January 2019 Abstract Let n, q and r be positive integers, and let KN be the n-skeleton of an (N - 1)-simplex. We show that for N sufficiently large every embedding of Kr^ in M2n+1 contains a link consisting of r disjoint n-spheres, such that every pairwise linking number is a nonzero multiple of q. This result is new in the classical case n =1 (graphs embedded in R3) as well as the higher dimensional cases n > 2; and since it implies the existence of an r-component link with all pairwise linking numbers at least q in absolute value, it also extends a result of Flapan et al. from n =1 to higher dimensions. Additionally, for r = 2 we obtain an improved upper bound on the number of vertices required to force a two-component link with linking number a nonzero multiple of q. Our new bound has growth O(nq2), in contrast to the previous bound of growth O(Vn4"qn+2). Keywords: Intrinsic linking, complete n-complex, Ramsey theory. Math. Subj. Class.: 57Q45, 57M25, 57M15 1 Introduction In the early 1980s Sachs [11] and Conway and Gordon [1] proved that every embedding of the complete graph K6 in R3 contains a pair of disjoint cycles that form a nontrivial link, and Conway and Gordon also showed that every embedding of K7 in R3 contains a nontrivial knot. These facts are expressed by saying that K6 is intrinsically linked, and K7 is intrinsically knotted. Since then, a number of authors have shown that embeddings of larger complete graphs necessarily exhibit more complex linking behaviour, such as non-split many-component links [4, 6]; two component links with linking number large in absolute value [2]; and two component links with linking number a nonzero multiple of a given integer [5, 6]. Embeddings of larger complete graphs must also exhibit more E-mail address: c.tuffley@massey.ac.nz (Christopher Tuffley) ©® This work is licensed under https://creativecommons.org/licenses/by/4.0/ 332 Ars Math. Contemp. 16 (2019) 331-348 complicated knotting behaviour, such as knots with second Conway co-efficient large in absolute value [2]. Such Ramsey-type results for intrinsic linking can also be shown to hold in higher dimensions. Let KN be the n-skeleton of an (N — 1)-simplex, which we call the complete n-complex on N vertices. Then Knn+4 is intrinsically linked, in the sense that every embedding in M2n+1 contains a pair of disjoint n-spheres that have nonzero linking number [10, 12]; and moreover, the linking results described above can all be extended to embeddings of sufficiently large complete n-complexes in M2n+1 [13]. Flapan, Mellor and Naimi [3, Theorem 1] have shown that intrinsic linking of graphs is arbitrarily complex, in the following sense: Given positive integers r and a, every embedding of a sufficiently large complete graph in R3 contains an r-component link in which the linking number of each pair of components is at least a in absolute value. The main goal of this paper is to prove an analogue of this result in all dimensions, with the condition on the magnitude of the linking numbers replaced by a divisibility condition instead. Namely, we show that, given positive integers r and q, every embedding of a sufficiently large complete n-complex in R2n+1 contains a link consisting of r disjoint n-spheres, in which all pairwise linking numbers are nonzero multiples of q. This result is new in the classical case n = 1 as well as the higher dimensional cases n > 2. Since a nonzero multiple of q has magnitude at least q, it also extends the Flapan-Mellor-Naimi result to n > 2. The techniques used to prove it draw heavily on those of Flapan, Mellor and Naimi (for the construction of many-component links with all pairwise linking numbers nonzero), as well as those of our previous paper [13] (for intrinsic linking with n > 2, and constructing links with linking numbers divisible by q). By refining a technique from [13] we also obtain a vastly improved upper bound on the number of vertices required in the case r = 2. Our new bound has growth O(nq2), in contrast to the previous best bound [13, Theorem 1.4] of growth O(^n4"q"+2). We note that Flapan, Mellor and Naimi [3, Theorem 2] further show that intrinsic linking of complete graphs is arbitrarily complex in an even stronger sense: one can additionally require that the second co-efficient of the Conway polynomial of each component has absolute value at least a as well. As an integral measure of the complexity of a knot, the second Conway co-efficient may be regarded as the natural analogue of the pairwise linking number, viewed as an integral measure of the complexity of a two-component link. By Hoste [7, Lemma 2.1(i)] the Conway polynomial V L (z) of an oriented r-component link L = K1 U K2 U • • • U Kr has the form V l(z) = zr-1[ao + a1z2 + • • • + amz2m ], and by the second Conway co-efficient we mean the co-efficient a1. When L = K1 is a knot we have a0 = 1 (Kauffman [9, Proposition 4.1], or see Hoste [7, Lemma 2.1(iii)]), so a1 is the first nontrivial co-efficient of VL(z); and when L = K1 U K2 is a two-component link we have a0 = ^k(K1, K2) (Hoste [7, Lemma 2.1(iv)]), so here it is the linking number that is the first nontrivial co-efficient of VL (z). Moreover, for a knot K the mod two reduction of a1 is equal to the Arf invariant of K (Kauffman [9, Section 4(a)], or see [7, Lemma 2.1(iii)]), so the linking number and the second Conway co-efficient may both be regarded as integral lifts of the mod two invariants used to establish the first results in intrinsic knotting and linking: the intrinsic linking of K6 is proved by considering a sum of pairwise linking numbers mod two, and the intrinsic knotting of K7 is proved by considering the sum of the Arf invariants of the Hamiltonian cycles in an embedding of K7 C. Tuffley: Intrinsic linking with linking numbers of specified divisibility 333 in R3 [1]. We do not consider knotting of the components in this paper. This is chiefly for reasons of dimension: knotting of n-spheres occurs in Rn+2, whereas linking of n-spheres occurs in r2k+i, so the only dimension in which we can consider intrinsic knotting and linking of n-complexes simultaneously is the classical case n =1. We have not given this case separate consideration, instead giving uniform arguments that work for all n. To our knowledge there are at present no known divisibility results for intrinsic knotting, and we pose the following question: Question 1.1. Let q > 2 be a positive integer. Does there exist N such that every embedding of Kn in R3 contains a knot with second Conway co-efficient a nonzero multiple of q? Hoste [8] shows that the first Conway co-efficient a0 of an r-component oriented link L is equal to any cofactor of a certain matrix of pairwise linking numbers associated with L. It then follows from Theorem 1.3 below that for N sufficiently large every embedding of Kn in R2n+1 contains a non-split r-component link satisfying a0 = 0 (mod q). As a strengthening of Theorem 1.3, we might additionally ask that a0 be nonzero, motivating the following question: Question 1.2. Let n, q and r be positive integers, with q > 2 and r > 3. Does there exist N such that every embedding of K^ in R2n+1 contains an r-component link with first Conway co-efficient a nonzero multiple of q? We conjecture that the answer to both questions above is yes. 1.1 Statement of results Throughout this paper, an r-component link means r disjoint oriented n-spheres embedded in R2n+1. Given a 2-component link L1 U L2 we will write ih(L1, L2) for their linking number, and £k2(L1,L2) for their linking number mod two. For {i,j} = {1,2} the integral linking number is given by the homology class [Li] in H„(R2n+1 - Lj; Z) = Z. Our main result is as follows: Theorem 1.3. Let n, q and r be positive integers, with r > 2. For N sufficiently large every embedding of Kn in R2n+1 contains an r-component link L1 U • • • U Lr such that, for every i = j, £k(Li, Lj) is a nonzero multiple of q. Since every nonzero multiple of q has absolute value at least q, Theorem 1.3 immediately gives us the following extension of Theorem 1 of Flapan et al. [3] to higher dimensions: Corollary 1.4. Let n, A and r be positive integers, with r > 2. For N sufficiently large every embedding of Kn in R2n+1 contains an r-component link L1 U • • • U Lr such that, for every i = j, \ik(Li, Lj)| > A. The r = 2 case of Theorem 1.3 is proved as Theorem 1.4 of [13], with an upper bound of growth O(Vn4"qn+2) on the number of vertices required. We re-prove this result with a greatly improved bound with growth O(nq2): 334 Ars Math. Contemp. 16 (2019) 331-348 Theorem 1.5. For r = 2, the conclusion of Theorem 1.3 holds for N > Kn(q) = 24 q2, n = 1, 4q2 (2n + 4) + n + i42^! + 1, n > 2. In other words, every embedding of (q) in M2n+1 contains a two component link L1 U L2 such that the linking number £k(L1, L2) is a nonzero multiple of q. We note that the bound of Theorem 1.5 is equal to the best known upper bound on the number of vertices required to force the existence of a generalised key ring with q keys (see Flapan et al. [3, Lemma 1] for the case n = 1 (although they don't state the bound explicitly), and Tuffley [13, Theorem 1.2] for n > 2). 1.2 Overview As is the case with most Ramsey-type results on intrinsic linking, Theorems 1.3 and 1.5 are proved by using the connect sum operation to combine simpler links into more complicated ones. To achieve the divisibility condition we will require the building block components to be "large", in the sense that they all contain two copies of a fixed suitably triangulated disc. The triangulation will not only need to have many n-simplices, but must also have a combinatorial structure analogous to a path in a graph. Accordingly, we call such a triangulated disc an n-path. We give a precise definition of a path in Section 2, and then re-establish a number of known results on intrinsic linking to show that we can require the necessary components to be large in this sense. The bulk of the work required to prove Theorem 1.3 is done in Proposition 3.1, which forms the main technical lemma of the paper. Section 3 is devoted to the proof of this. The proposition plays the role of Flapan, Mellor and Naimi's Lemma 2, and the statement and proof are heavily modelled on theirs, making modifications as needed for it to work in all dimensions and achieve the divisibility condition. From an arithmetic standpoint, realising the divisibility condition largely boils down to repeatedly applying the following simple number-theoretic observation, used by both Fleming [5] and Tuffley [13]: Let £1,£2,... ,£q be integers. Then there exist 0 < a 2, however, and it will not be sufficient to simply work with spheres with many vertices or n-simplices. Instead, we will additionally require our components to be large in the following sense, where D is chosen in advance: Definition 2.1. Let D be an n-dimensional triangulated disc. A triangulated n-sphere is large with respect to D or D-large if it contains two disjoint oppositely oriented copies of D. When it comes time to prove Theorem 1.3 we will choose D so that it has a triangulation of the following form: Definition 2.2. Let D be an n-dimensional triangulated disc with i n-simplices. Then D is a path of length i if its n-simplices may be labelled Ai,..., Ae such that b Dab = U Ai i=a is a disc for any 1 < a < b < i. For n = 1 this definition co-incides with the usual meaning of a path in a graph. To construct a path for n > 2 we may start with i n-simplices A1,..., A^, and choose distinct (n - 1)-simplices Si belonging to Aj. Choose simplicial isomorphisms ^ : Si ^ 7i+1 for 1 < i < i - 1, and glue the Ai according to the The result is a disc Dn, and the triangulation Dn = A1 U • • • U Ae satisfies Definition 2.2 by construction. In Lemma 2.6 of [13] it is shown that a disc constructed in this way has i + n vertices, and the number of (n - 1)-simplices in dDn is i(n - 1) + 2. We note that for n > 2 a path does not necessarily have this form: for instance, for n = 2 the triangulation of a regular n-gon by radii may be given the structure of a path. We begin by establishing the existence of D-large n-spheres with arbitrarily many additional n-simplices. For convenience, we let an (D, m) be the minimal number of vertices of a triangulated sphere satisfying the conditions of the following lemma. Lemma 2.3. Let D be a triangulated disc, and let m be a positive integer. There is a triangulation of Sn that contains two disjoint oppositely oriented copies of D, together with at least m additional n-simplices. Proof. Consider D x I. If V = {v0,..., vN} is the vertex set of D, then D x I has a triangulation with vertex set V x {0,1}, and simplices of the form Sj = [(vio, 0),..., (vij, 0), (vij, 1),..., (vifc, 1)] for 0 < j < k and each k-simplex S = [vio,..., vik] of D with i0 < i1 < • • • < ik. As a first pass we let S = d(D x I) with the induced triangulation. The n-sphere S contains two disjoint copies of D, namely D x {0} and D x {1}, and they are oppositely oriented because they are exchanged by reflection in the equator dD x {1}. Suppose that dD contains a total of t simplices of dimension n - 1. Each contributes a total of n simplices of dimension n to dD x I, so S has a total of nt additional n-simplices. If nt > m does not hold then let S' be a triangulated n-sphere with at least m - nt + 1 simplices of dimension n (such a triangulated sphere certainly exists, for example by taking the boundary of a sufficiently long (n + 1)-path, as constructed above). C. Tuffley: Intrinsic linking with linking numbers of specified divisibility 337 Choose n-simplices 5 and 5' belonging to dD x I and S', respectively, and form the connected sum of S and S' by gluing the discs S - 5 and S' - 5' along their boundaries. The resulting sphere satisfies the conditions given in the conclusion of the lemma. □ We now use Lemma 2.3 to prove the existence of generalised key rings with large rings. To do this we require the following slight strengthening of Lemma 3.2 of [13], which is in turn an extension of Lemma 1 of Flapan et al. [3] to all dimensions. Lemma 2.4. Let D be a triangulated disc. Suppose that KN is embedded in R2n+1 such that it contains a link L U J1 U • • • U Jm2 U X1 U • • • U Xm2, where ¿k2( Jj, Xj) = 1 for all i, and L contains two disjoint oppositely oriented copies of D and at least m2 additional n-simplices. Then there is an n-sphere Z in KN with all its vertices on L U J1 U • • • U Jm2, and an index set I with |I| > mm, such that ^k2(Z, Xj) = 1 for all j G I and Z contains two disjoint oppositely oriented copies of D. In Lemma 3.2 of [13] we require only that L has at least m2 n-simplices. Thus, the difference between the two results is the stronger condition that L contains the two copies of D and a further m2 n-simplices, and the additional conclusion that Z contains two disjoint oppositely oriented copies of D. To prove the stronger form it is only necessary to observe that in proving the original result we can ensure that the copies of D in L end up in Z. Proof. The first step in the proof of [13, Lemma 3.2] is to construct an n-sphere S with all its vertices on L U J1 U • • • U Jm2, and meeting each sphere Jj in an n-simplex S.j. This is done by choosing a distinct n-simplex Sj belonging to L for each i = 1,..., m2, and applying [13, Corollary 2.2] to obtain a sphere Qj C KN with all its vertices on Sj U S-, and meeting Jj in Sj and L in Sj. The sphere S is then constructed from L and the Qj by omitting the interiors of the discs S-. Thus, we can ensure that S contains two disjoint oppositely oriented copies of D by choosing the S- from among the m2 additional n-simplices of L, leaving the copies of D intact. At the final step in the proof of [13, Lemma 3.2], the required sphere Z is constructed from S and a (possibly empty) subset of the Jj, by omitting the interiors of the corresponding n-simplices Sj. Therefore, since S contains the required copies of D, we are guaranteed that Z does too. □ Corollary 2.5. Let D be a triangulated disc, and r a positive integer. For N sufficiently large, every embedding of KN in R2n+1 contains an (r + 1)-component link R U L1 U • • • U Lr such that ¿k2 (R, Lj) = 1 for all i, and R contains two disjoint oppositely oriented copies of D. It suffices to take N > Kn(D, r) = 4r2(2n + 4) + a„(D, 4r2). Proof. Given an embedding of K^(D r) in R2n+1, choose 4r2 disjoint copies of Kn„+4 contained in the embedding, together with a copy of K^(D 4r2). By Taniyama [12] the ith copy of K2nn+4 contains a 2-component link Jj U Xj such that ^k2( Jj, Xj) = 1, and the copy of Kff" (D 4r2) contains a triangulated sphere L that contains two disjoint oppositely 338 Ars Math. Contemp. 16 (2019) 331-348 oriented copies of D and at least 4r2 additional n-simplices. The result now follows by applying Lemma 2.4 with m = 2r to the link L U Ji U • • • U J4r2 U Xi U • • • U X4r2. □ Finally, we extend Proposition 1 of Flapan et al. [3] to higher dimensions, with the additional conclusion that all components are large with respect to a chosen triangulated disc D. This result serves as the base case for the inductive argument proving Theorem 1.3 in Section 4. Proposition 2.6. Let D be a triangulated disc, and let r be a positive integer. For N sufficiently large, every embedding of K^ in R2n+i contains a 2r-component link Ji U • • • U Jr U Li U • • • U Lr, such that ¿k2(Ji, Lj) is nonzero for all i and j, and each component contains two disjoint oppositely oriented copies of D. The link given by this result has mod two linking pattern containing the complete bipartite graph Kr r, because each component Ji has nonzero mod 2 linking number with each component Lj. The argument to prove the existence of such a link is exactly that of Flapan et al.'s proof of their Proposition 1, and the extension to higher dimensions already follows from our paper [13]: as noted in Section 1.2.2 of [13] their Proposition 1 is a purely combinatorial argument that depends only on their Lemma 1 and the existence of generalised key rings, and these are generalised to higher dimensions in [13]. So the work to be done here is to ensure that each component contains copies of the disc D. For n =1 this already follows from Flapan et al.'s Proposition 1, because we may simply subdivide each edge of a sufficiently large complete graph into paths of length I. A similar approach could be taken in higher dimensions, using the subdivisions of K^ constructed in [13], but this introduces many unnecessary vertices. We give a simpler argument that doesn't make use of subdivision, and requires far fewer vertices. Proof. Following Flapan et al. [3] let m = ^—, and let N = mKn(D, r) + ra„(D, m). Then K^ contains m copies of K^(D r) and r copies of K^(D m), all disjoint from one another. Given an embedding of K^ in R2n+i, by Corollary 2.5 the ith copy of Krn (D r) contains a generalised key ring n Ri U Jii U • • • U Jir such that the ring R is D-large; and the jth copy of K^ (D m) contains a D-large sphere Lj that contains at least m additional n-simplices. n Apply Lemma 2.4 to the link Li U Jii U • • • U Jmi U Ri U • • • U R„. This yields a D-large sphere Zi with all its vertices on Li U Jii U • • • U Jmi, and an index set Ii with |1i| > ^T = ^— = mi, such that ^2(Zi,Ri) = 1 for all i G Ii. Suppose now that for some 1 < k < r we have constructed D-large spheres Zi,..., Zk and an index set Ik such that C. Tuffley: Intrinsic linking with linking numbers of specified divisibility 339 (1) all vertices of Zj lie on Lj U Jj U • • • U Jmj for 1 < j < k; (2) IIk | > mk = i4^; (3) ik2(Zj, Ri) = 1 for all 1 < j < k and i G Ik. Applying Lemma 2.4 to the link Lk+i u i (j Ji(k+iH ul u Ri j Vie/fc / Vie/fc / we obtain a D-large sphere Zk+1 with all its vertices on Lk+1 U J1(k+1) U • • • U Jm(k+1), and an index set Ik+1 C Ik with |Ik+1| > = (4r) 4- = mk+1, such that ik2(Zk+1, R) = 1 for all i G Ik+1. This gives us D-large spheres Z1,..., Zk+1 and an index set Ik+1 such that conditions (1)-(3) hold with k replaced by k + 1, so by induction there are D-large spheres Z1,...,Zr and an index set Ir such that they hold for k = r. Since mr = (4r)4— = r, the first 2r components of Z1 U • • • U Zr U ^ J Ri j are the required link. □ 3 The main technical lemma This section is dedicated to proving the following analogue of Lemma 2 of Flapan et al. [3], which forms the main technical lemma of this paper: Proposition 3.1 (Main technical lemma). Let q G N. Suppose that Kn is embedded in R2n+1 such that it contains a link with oriented components Ji,..., JA, Li,..., LB, X1,..., XS and Y1,... ,YT satisfying (1) A > 2sqS+T; (2) B > 3s2t(S + T)qS+T; (3) £k(Ja,Xs) is nonzero for all a and s; (4) lk(Lb, Yt) is nonzero for all b and t; and (5) each component Ja, Lb contains two disjoint oppositely oriented copies of a fixed path D of length A > (2q)S+T. Then Kn contains an n-sphere Z with all its vertices on J1 U • • • U JA U L1 U • • • U LB such that, for each s and t, £k(Z, Xs) and tk(Z, Yt) are nonzero multiples of q. We note that the hypotheses of our Proposition 3.1 are much stronger than the hypotheses of Flapan et al.'s Lemma 2: we require A and B to be much greater, and we have the additional hypothesis (5) that the components Ja, Lb are large with respect to a certain path. This is to be expected, since our conclusion is strictly stronger than theirs: any nonzero multiple of q is necessarily at least q in magnitude. Before proving Proposition 3.1 we first establish the following lemma on sums of vectors in Rd, which we will use in the proof. 340 Ars Math. Contemp. 16 (2019) 331-348 Lemma 3.2. Let f G Rd be a vector with all entries nonzero, and for i = 0,..., N let vi G Rd. If N > 2d then there exist 0 < j < k < N such that every entry of f + vk — Vj is nonzero. Proof. The proof is by induction on d. In the base case d = 1, suppose that N > 2. If either f + v, — v0 or f + v2 — v, is nonzero then we are done, and otherwise f + v2 — vo = (f + v2 — vi) + (f + vi — vo) — f = —f = 0. Thus the lemma holds in the base case d =1. Suppose now that the lemma holds for some d > 1, and let v0, v1,..., vN be N + 1 > 2d+1 + 1 vectors in Rd+1. We claim that there is N' > 2d and N' + 1 indices 0 < i0 < i1 < • • • < iN' < N such that, for any 0 < j < k < N', the (d + 1)th entry of f + vik — vij is nonzero. The inductive step will then follow by applying the inductive hypothesis to the first d entries of f and vi0,..., viN,. Write x(i) for the ith entry of x G Rm. To prove the claim we consider the graph with vertex set {0,1,..., N}, and an edge between j and k if j < k and the difference 4d+1) — vjd+1) is equal to the forbidden value —f(d+1). Now observe that for any path (i0, i1,..., im) in this graph we have m— 1 v(m+1)—vid+1)=E[v?+1)—v£1)]=—f(d+1) t sign(ij—ij—1). In particular, if the path is a cycle then im = io, and it follows that m—1 fd+1 T sign(ij+i — ij) = 0. j=i Since f(d+1) is nonzero by hypothesis the sum must be zero, and since each term is ±1, for this to occur it must involve an even number of terms. Thus any cycle must be of even length, and it follows that our graph is bipartite. Colour the vertices black and white in such a way that there is no edge between vertices of the same colour, and let 0 < i0 < i, < • • • < iN/ < N be the vertices belonging to the larger colour class. Then N' + 1 > |"(N + 1)/2] > |~(2d+1 + 1)/2] = 2d + 1, and for any 0 < j < k < N' we have f(d+1) + v(d+1) — v(d+1) = 0, as required. Lemma 3.2 now follows by our discussion above. □ ProofofProposition 3.1. Let J = J, u • • • u ja, X = X, u • • • u xs , L = L, U---U lb , Y = Yi u^^^u yt. Following Flapan et al. [3], we begin by replacing the links J and L with sublinks J', L'' for which we have some control over the signs of the entries of the linking matrices ^k( J', X), ^k(L'', Y) and ^k(L'', X). To do this, we first consider the patterns of signs of the entries of the vectors ^k( Ja, X). Since these vectors have S entries, and all are nonzero, there are 2S possibilities for the patterns of signs (positive and negative) in each one. It follows that we can choose at least A/2S > qS+T of them that all have the same pattern of C. Tuffley: Intrinsic linking with linking numbers of specified divisibility 341 signs. Moreover, after reversing the orientation of some components of X if necessary, we may assume that these signs are all positive. Thus, setting J' = J1 U • • • U Jqs+T, we may assume without loss of generality that the linking matrix ^k( J', X) is positive. Applying the same argument to the vectors ¿k(Lb, Y), we obtain a sublink L' of L with at least 3S(S + T)qS+T components such that the linking matrix ik(C, Y) is positive. We now consider the patterns of signs (positive, negative or zero) of the vectors ¿k(Lb, X) for Lb a component of L'. There are now 3S possibilities for these patterns, so we may choose at least (S + T)qS+T components that have the same pattern. Setting L'' = L U • • • U )qs+T we may therefore assume without loss of generality that the linking matrix ^k(L'', Y) is positive, and that each column of ^k(L'', X) is either positive, negative, or zero. From now on we restrict our attention to the sublinks J' and L'' of J and L. Our next goal is to construct a sublink Z = Z1 U • • • U ZC of J' U L'' such that every entry of C z = ^ ¿k(Zc, X U Y) c=1 is a nonzero multiple of q. At the final step we will obtain the required n-sphere Z as a connect sum of the components of Z. To this end we begin by considering the sums a ja = ^ ¿k(J0, X U Y) a=1 modulo q for 1 < a < qS+T. Each vector ja has S + T entries, so there are qS+T possibilities when considered mod q. Since we have qS+T vectors in total, by the pigeonhole principle we can either find one that is zero modulo q, or two that are equal modulo q. In either case, there are integers 0 < a0 < a1 < qS+T such that the vector ai j = ^ ¿k(Ja, X U Y) a=ao + 1 is zero modulo q. Moreover, the first S entries of j are given by J2 a= a+1 ^k( Ja, X), and are therefore nonzero, because the vector ^k( Ja X) is positive for each a. We will use Jao+1 U • • • U Jai as the first a1 - a0 components of Z. We now consider the sums £ ^k(L6, X U Y) b=1 modulo q for 1 < A < (S + T)qS+T. Since there are again qS+T possibilities mod q, and we have (S + T)qS+T sums in total, we can either find S + T of them that are zero mod q, or S + T + 1 of them that are identical mod q. In either case, there are integers 0 < Ao < A1 < • • • < As+t < (S + T)qS+T such that the vectors ft ¿i = ^ ¿k(Lb, X U Y) b=£o + 1 are zero modulo q. Any additional components of Z will be chosen from among L^0+1 U L£o + 2 u • • • u l£s+T . 342 Ars Math. Contemp. 16 (2019) 331-348 To choose the remaining components of Z we consider the sequence of S + T + 1 vectors j, j + £1,..., j + £s+t. From above these vectors are all zero when considered modulo q, and we claim that it is possible to choose at least one of them that is nonvanishing when considered as an integer vector. To see this, consider first the (S+t)-entries for some 1 < t < T, which are given by a 1 j(S+t) = £ *HJa,Yt), a=a0 + 1 ai Pi (j + ii)(S+t) = £ ik(Ja,Yt)+ £ lk(Lb, Yt). a=ao + 1 b=Po + 1 Since the linking matrix £k(C", Y) is positive these form a strictly increasing sequence, and consequently the (S +1)-entry vanishes for at most one of our S + T + 1 vectors. Next, consider the s-entries for some 1 < s < S, which are given by a1 j(s) ik(Ja,Xs), a=ao + 1 ai Pi (j + ti)(s) = £ ik(Ja,Xs)+ £ ik(Lb,Xs). a=ao + 1 b=Po + 1 Recall that the first sum is positive, and that each column of the linking matrix £k(C", X) is either positive, negative, or zero. It follows that the above sequence of integers is either constant (in which case it is positive), or it is strictly increasing or strictly decreasing. In any case we again conclude that the s-entry vanishes for at most one of our S + T +1 vectors. Thus there are at most S + T vectors for which one of the entries vanishes, and so there is at least one for which no entry vanishes, proving the claim. We may then set z = z1 u • • • u zc {Jao+1 U • • • U Jai if j is nonvanishing, or Jao+1 U • • • U Jai U Lpo+1 U • • • U Lpi if j + £j is nonvanishing. With this choice of Z, every entry of C zo = ^ ik(Zc, X U Y) c=1 is a nonzero multiple of q, as required. Our final task is to obtain the required n-sphere as a suitable connect sum of the components of Z. To do this we will inductively construct oriented spheres F1,..., FC-1 such that, for each 1 < y < C - 1, (a) the vertices of FY lie on ZY U Z1+1 (and so FY is disjoint from X, Y, and the rest of Z); (b) Fy-1 n ZY and FY n ZY are disjoint discs, each of which is oppositely oriented by ZY and Fy-1 or FY; C. Tuffley: Intrinsic linking with linking numbers of specified divisibility 343 (c) every entry of the vector Y z7 = zo + ^ XUY) ¿=1 is a nonzero multiple of q. We will then obtain the required sphere Z from the union of Z and the Fc by omitting the interiors of the discs Fc n Zc and Fc n Zc+1. Conditions (a) and (b) imply that Fc and Fc are disjoint for all c and c', and it follows that Z is a connect sum of spheres, and hence itself a sphere. Moreover, as a chain we have Z = J2 C=1 Zc + J2Fc, so C-1 ¿fc(Z, XUY) = z0 + ^ ^k(Fc, X U Y), c=1 and by condition (c) every entry of this vector is a nonvanishing multiple of q. The underlying technique for constructing the spheres Fc comes from the proof of Theorem 1.4 of Tuffley [13], but additional work is required to ensure that condition (c) is satisfied. By hypothesis (5) each sphere Zc contains two disjoint copies of the path D, one of each orientation. We begin by labelling these Dc and Dc' in such a way that there is an orientation reversing simplicial isomorphism : Dc ^ D'c +1. This may be done inductively: first label the copies of D contained in Z1 arbitrarily, and then once Dc and Dc have been chosen, choose Dc+1 and Dc+1 so that D'c +1 is oppositely oriented to Dc. We will choose the spheres Fc so that the following strengthened form of condition (a) holds for 1 < y < C - 1: (a') the vertices of FY lie on DY U DY +1. This condition serves to ensure that FY-1 n ZY and FY n ZY are disjoint, as required by condition (b). Suppose that for some 0 < c < C - 1 the spheres F,..., Fc have been constructed so that conditions (a'), (b) and (c) hold for 0 < y < c. When c = 0 conditions (a') and (b) are empty, and condition (c) is that every entry of z0 is a nonzero multiple of q, so we may take c = 0 as our base case. Let A1;..., Aa be a labelling of the n-simplices of the path Dc+1 as in Definition 2.2, and for 1 < I < A let P^ be the oriented sphere satisfying Pe n Zc+1 = a£, p£ n Zc+2 = ^c+1(A£) that results from applying Corollary 2.2 of Tuffley [13] to the pairs (Zc+1, Dc+1) and (Zc+2, Dc+2). The vertices of these spheres all lie on Dc+1 U D'c+2, and for any 1 < ^ < v < A, the chain J2V=M P^ represents a sphere meeting Dc+1 in the disc |JV=M A^, and Dc+2 in the disc UV=M ^+1^). For 1 < I < A we consider the sums ^ XUY) ¿=1 modulo q. As above there are qS+T possibilities for these modulo q, and we have A > 2s+tqS+T of them, so we can either find 2S+T of them that are identically zero mod q, or 344 Ars Math. Contemp. 16 (2019) 331-348 2s+t + 1 of them that are equal mod q. In either case there are integers 0 < m0 < Mi < • • • < M2S+T such that the vectors Mj Pj = £ ik(pi,XUY) i=Mo + 1 are identically zero mod q for 1 < j < 2S+T. Set p0 = 0, and apply Lemma 3.2 to the vectors p0, p1;..., p2s+T G RS+T with f = zc. This yields indices 0 < j < k < 2S+T such that no entry of Mk zc + pfc - pj = zc + £ ek(Pu XUY) i=Mj + 1 is zero. Moreover, the vectors zc, pj and pk are all identically zero mod q, so every entry of zc + pk - pj is a nonzero multiple of q. Let Fc+1 = J2i=Mj+1 Pi. Then Fc+1 represents an n-sphere with all its vertices on Zc+1 U Zc+2, and meeting Zc+1 and Zc+2 in the discs Fc+1 n Zc+1 = U Ai C Dc+1, Fc+1 n Zc+2 = ^c+1 I U Ai) g DC+2. i=Mj + 1 \i=Mj + 1 J The construction of Corollary 2.2 of Tuffley [13] ensures that these discs are oppositely oriented by Fc+1 and Zc+1 U Zc+2, so conditions (a') and (b) are satisfied; and with this choice of Fc+1 we have zc+1 = zc + pk - pj, so condition (c) is too. This completes the inductive step, and we now obtain the required sphere Z as described above. □ 4 Proof of Theorem 1.3 We are now in a position to prove our main result, Theorem 1.3. The strategy is that of Flapan et al.'s proof of their Theorem 1. Proof of Theorem 1.3. Following Flapan et al. [3], for each u,v G N let H (u, v) denote the complete (u + 2)-partite graph with parts P1 and P2 containing v vertices each, and parts Q1,... ,Qu containing a single vertex each. We will prove by induction on u that for every u > 0 and v, i > 1, for N sufficiently large every embedding of in R2n+1 contains a link L such that (L1) the linking pattern of L contains the graph H(u, v); (L2) the linking number between any two distinct components in Q1 U • • • U Qu is a nonzero multiple of q; and (L3) every component in P1 U P2 contains disjoint oppositely oriented copies of a path D of length at least i. For simplicity, we will say that a link L satisfying conditions (L1)-(L3) with the given parameter values satisfies property (u, v, i). C. Tuffley: Intrinsic linking with linking numbers of specified divisibility 345 The base case u = 0 follows from Proposition 2.6 with r = v, by choosing D to be a path of length I. Suppose then that the claim holds for some u > 0. Given v, I > 0, let S = v, T = u + v, A = B = 2T3s(S + T)qS+T > 2sqS+T, A = max{^, (2q)S+T}, and let w = S + A = S + B. By our inductive hypothesis, for N sufficiently large every embedding of KN in R2n+1 contains a link L satisfying property (u, w, A). We will show that every such embedding also contains a link L' satisfying property (u + 1, v, I). Given an embedding of KN in R2n+1 and a link L contained in it satisfying property (u, w, A), label the components of L such that P1 = {x1,...,xs ,l1,...,lB }, P2 = {Y1,... ,ys ,J1,..., J A}, and Qi = {Yv+i} for 1 < i < u. Then all linking numbers lk(Ja, Xs) and £k(Lb, Yt) are nonzero by (L1), and every component Ja, Lb contains two disjoint copies of a path D of length at least A > (2q)S+T, by (L3). So we may apply Proposition 3.1 to L to obtain a sphere Z with all its vertices on J1U • • • U JA U L1U • • • U LB and linking every component Xs, Yt with linking number a nonzero multiple of q. Let l' = x1 u • • • u xs u y1 u • • • u yt u z = x1 u • • • u xv u y1 u • • • u yu+v u z, and partition the components as P{ U P2' U Q[ U • • • U QU+1 such that and Pi = {Xi,...,Xv }, f {Yv+i} 1 < i < u, 1 {Z} i = u +1. Then with respect to this partition the linking pattern of L contains the graph H(u + 1, v); any two components in Q1 U • • • U Q'u+1 have linking number a nonzero multiple of q; and every component in P1 U P2 contains a copy of D, which is a path of length at least A > I. So L satisfies property (u + 1, v, I), completing the inductive step. By (L2) the result now follows by restricting attention to Q1 U • • • U Qu, with u = r. □ 5 The two component case We now turn to the two component case, and establish the improved bound of Theorem 1.5. From the proof of [13, Theorem 1.4] it suffices to prove every embedding of K^ contains a generalised key ring with q keys each large with respect to a path D of length q. The approach of [13] was to work with a subdivision of KN, in which each n-simplex was subdivided into qn simplices. This is a fairly extravagant approach, since only 2q 346 Ars Math. Contemp. 16 (2019) 331-348 n-simplices from each component are used to form the required paths. The reduction in the number of vertices required comes from Lemma 5.1, which gives us a simple and economical way to enlarge the keys of an existing generalised key ring. A further modest saving comes from "recycling" some of the vertices leftover from the construction of the initial key ring. Lemma 5.1. Let KN be embedded in M2n+1 such that it contains a link X U Y with ¿k(X, Y) = 0. Let D be a triangulated n-disc with d vertices, and suppose that V is a set of 2d — (n +1) vertices of KN disjoint from X U Y. Then KN contains a D-large sphere Z with all its vertices on Y U V such that ¿k(X, Z) = 0. The result also holds with all linking numbers calculated mod 2. Proof. Choose an n-simplex A belonging to Y, and let S = d(D x I) with the triangulation with 2d vertices from the proof of Lemma 2.3. Then A U V contains a total of (n+1) + (2d — (n+1)) = 2d vertices, so we may embed S in K^ such that all vertices of S lie on A U V and A is an n-simplex of dD x I. Orient S such that A receives opposite orientations from S and Y, and consider the chains S and T = S + Y. Both represent D-large n-spheres with all their vertices on Y U V, and the linking numbers ¿k(X, S), ¿k(X, T) cannot both be zero because in the homology group ff„(R2n+1 — X) we have [T ] — [S] = [S + Y ] — [S] = [Y ]=0. (5.1) We may therefore choose one of S and T to be Z so that ¿fc(X, Z) = 0. If ^2(X, Y) = 0 then equation (5.1) holds in F„(R2n+1 — X; Z/2Z), and we may again choose Z to be one of S and T so that ¿k2 (X, Z) = 0. □ Corollary 5.2. Let q be a positive integer. Then every embedding of K^ (q) in M2n+1 contains a generalised key ring in which each key is large with respect to a path D of length q. Proof. By [13, Theorem 1.2] every embedding of K^(q) in R2n+1 contains a generalised key ring L with q keys. This link is constructed by applying [13, Lemma 3.2] (the extension of [3, Lemma 1] to higher dimensions) to a link L U J1 U • • • U J4q2 U K1 U • • • U K4q2, in which ^k2( Jj, Kj) is nonzero for all i, and each component Jj, Kj is the boundary of an (n + 1)-simplex. This yields an n-sphere R with all vertices on L U J1 U • • • U J4q2 and linking at least q of the Kj, which forms the ring of the generalised key ring. Let Kj1,..., Kjq be the keys. Recall that a path D of length q can be constructed using as few as d = q + n vertices. Since only q of the Kj are components of L this leaves at least (4q2 — q)(n + 2) = q(4q — 1)(n + 2) vertices of K^ (q) that do not belong to L. Observe that (4q — 1)(n + 2) = (4q — 1)n + 8q — 2 > 2n + 2q = 2d > 2d — (n + 1). The spare vertices are therefore more than enough to apply Lemma 5.1 q times to R and each key Kjj in turn, replacing Kjj with a D-large sphere Zj that still links R. Then r u z1 u • • • u z, q is the desired link. □ C. Tuffley: Intrinsic linking with linking numbers of specified divisibility 347 For completeness' sake we sketch the steps needed to prove Theorem 1.5 from this point. For any missing details see the proof of [13, Theorem 1.4], or the corresponding step of the proof of Proposition 3.1. Proof of Theorem 1.5. By Corollary 5.2, every embedding of Kn (q) in M2n+1 contains a generalised key ring R U Z1 U • • • U Zq such that each key Zj is large with respect to a path D of length q. Orient the Zj so that all linking numbers with R are positive. Working in the homology group H„(M2n+1 - R; Z), let 1 < a < b < q be such that ¿[Zj] = 0 (mod q), and note that this sum is positive. From now on we restrict our attention to the spheres Za, . . . , Zb. If a = b we are done. Otherwise, we use the fact that each component Zj is D-large to construct oriented spheres Fa,..., Fb-1 such that, for a < i < b - 1, (a) the vertices of Fj lie on Zj U Zj+1 (and so Fj is disjoint from R and the rest of the Zj); (b) Fj-1 n Zj and Fj n Zj are disjoint discs, each of which is oppositely oriented by Zj and Fj-1 or Fj; (c) the linking number ¿k(R, Fj) is zero mod q. The construction of the Fj is identical to that of the corresponding spheres in Proposition 3.1, except that the simpler condition (c) means we only require D to have length q, and the spheres can all be constructed simultaneously instead of inductively. Now if ¿k(R, Fj) is nonzero for some i then R U Fj is the required link; and otherwise, we let Z be the connect sum of Za,..., Zb, Fa,..., Fb-1 obtained by omitting the interiors of the discs Fj n Zj and Fj n Zj+1 for each i. Then Z is an n-sphere, and in ff„(R2n+1 - R) we have b b-1 b [Z ] = ¿[Zj] + ¿[Fj] = ¿[Zj], i=a j=a j=a which is a nonzero multiple of q. □ References [1] J. H. Conway and C. McA. Gordon, Knots and links in spatial graphs, J. Graph Theory 7 (1983), 445-453, doi:10.1002/jgt.3190070410. [2] E. Flapan, Intrinsic knotting and linking of complete graphs, Algebr. Geom. Topol. 2 (2002), 371-380, doi:10.2140/agt.2002.2.371. [3] E. Flapan, B. Mellor and R. Naimi, Intrinsic linking and knotting are arbitrarily complex, Fund. Math. 201 (2008), 131-148, doi:10.4064/fm201-2-3. [4] E. Flapan, J. Pommersheim, J. Foisy and R. Naimi, Intrinsically n-linked graphs, J. Knot Theory Ramifications 10 (2001), 1143-1154, doi:10.1142/s0218216501001360. [5] T. Fleming, Intrinsically linked graphs with knotted components, J. Knot Theory Ramifications 21 (2012), 1250065 (10 pages), doi:10.1142/s0218216512500654. 348 Ars Math. Contemp. 16 (2019) 331-348 [6] T. Fleming and A. Diesl, Intrinsically linked graphs and even linking number, Algebr. Geom. Topol. 5 (2005), 1419-1432, doi:10.2140/agt.2005.5.1419. [7] J. Hoste, The Arf invariant of a totally proper link, Topology Appl. 18 (1984), 163-177, doi: 10.1016/0166-8641(84)90008-7. [8] J. Hoste, The first coefficient of the Conway polynomial, Proc. Amer. Math. Soc. 95 (1985), 299-302, doi:10.2307/2044531. [9] L. H. Kauffman, The Conway polynomial, Topology 20 (1981), 101-108, doi:10.1016/ 0040-9383(81)90017-3. [10] L. Lovasz and A. Schrijver, A Borsuk theorem for antipodal links and a spectral characterization of linklessly embeddable graphs, Proc. Amer. Math. Soc. 126 (1998), 1275-1285, doi: 10.1090/s0002-9939-98-04244-0. [11] H. Sachs, On a spatial analogue of Kuratowski's theorem on planar graphs—an open problem, in: M. Borowiecki, J. W. Kennedy and M. M. Syslo (eds.), Graph Theory, Springer, Berlin, volume 1018 of Lecture Notes in Mathematics, pp. 230-241, 1983, doi:10.1007/bfb0071633, proceedings of a conference held in Lag6w, February 10 - 13, 1981. [12] K. Taniyama, Higher dimensional links in a simplicial complex embedded in a sphere, Pacific J. Math. 194 (2000), 465-467, doi:10.2140/pjm.2000.194.465. [13] C. Tuffley, Some Ramsey-type results on intrinsic linking of n-complexes, Algebr. Geom. Topol. 13 (2013), 1579-1612, doi:10.2140/agt.2013.13.1579.