transactions of the american mathematical society

Volume 324, Number 2, April 1991

RAMSEY THEOREMS FOR KNOTS, LINKS AND SPATIAL GRAPHS

SEIYA NEGAMI
Abstract. An embedding f: G R of a graph G into R is said to be linear if each edge f(e) (e G E(G)) is a straight line segment. It will be shown that for any knot or link type k , there is a finite number R(k) such that every linear embedding of the complete graph Kn with at least R(k) vertices (n > R(k)) in R contains a knot or link equivalent to k .

1. Introduction
A link is a disjoint union of a finite number of simple closed curves in the three-dimensional Euclidean space R3. In particular, a link with only one component is called a knot. A knot k is said to be trivial if k bounds a 2-cell in R and equivalently if there is a homeomorphism h : R > R which carries k onto the unit circle in the xy-plane {(x, y, 0) G R3 : x, y e R} . Also a link k is said to be trivial if there is a homeomorphism h : R -*R such that h(k) is contained in the xy-plane. In other words, a trivial link is a union of mutually

unlinked trivial knots. Two knots (or links) kx and k2 are said to be equivalent or to have the same knot type (or link type) if there is a homeomorphism h : R - R such that //(/c,) = k2. An ambient isotopy of R3 is a continuous map H: R3 x / -> R3 such that //, is a homeomorphism for any / G / and H0 is the identity map,
and Ht : R * R is a map defined by Ht(x) = H(x. t). Two links kx and k2 are said to be ambient isotopic if there is an ambient isotopy H: R x I R3 such that Hx(kx) = k2. (See [Ro] for the terminology of knot and link theory.) On the other hand, a graph G is a 1-dimensional simplicial complex or the underlying space of such a complex and each 0-simplex and 1-simplex are called a vertex and an edge of G, respectively. In particular, the 1-skeleton of an (n - 1)-simplex is called the complete graph on n vertices and is denoted by Kn . In other words, the complete graph Kn is a graph such that any two vertices are joined by an edge. We denote the vertex set and edge set of a graph
Received by the editors October 19, 1987. 1980 Mathematics Subject Classification (1985 Revision). Primary 57M25; Secondary 05C55, 57M15, 05C10. Key words and phrases. Knots, links, spatial graphs, Ramsey theory.
1991 American Mathematical Society

where / stands for the unit interval [0,1]

0002-9947/91 $1.00+ $.25 per page

527
License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use

528

SEIYANEGAMI

G by V(G) and E(G), respectively. (See [BM] for the terminology of graph theory.) A cycle C in a graph G is a cyclic sequence {v0, ... ,vn_x} of distinct
vertices of G such that any two consecutive vertices v and v+x, i taken modulo n , are joined by edge vv+x and is often regarded as a simple closed curve in the topological space G. So if one embeds G in R3 by an embedding

/:G-R , then the image of any cycle in G is a knot, trivial or not, and any disjoint union of cycles in G forms a link in R3. (We can find a combinatorial arguments on knots and links in graphs in [Sa].) We call an embedding /: G -* R3 of a graph G in R3 a spatial embedding of G and a graph f(G) embedded in R a spatial graph. We shall say that two spatial graphs are equivalent or ambient isotopic in the same sense as knots and links. As a typical phenomenon of spatial embeddings of graphs, Conway and Gordon have proved the following theorem in [CG]:

Theorem 1 (Conway-Gordon [CG]).

(i) Every spatial embedding of K6 contains a nontrivial 2-component link. (ii) Every spatial embedding of K1 contains a nontrivial knot.

This theorem says nothing about the types of such a link and a knot. What can we say if their link and knot types are specified? Our purpose in this paper is to answer this question. We would like to establish theorems in the same style as above. It is however impossible in general. For if one makes a local knot on each edge of Kn in R , then any cycle in Kn must have a specified knot type as its connected sum
factor. So we should restrict spatial embeddings of graphs so as to forbid such a phenomenon. A spatial embedding /: G > R is said to be linear if fi(e)

is a single straight line segment for each edge e e E(G). Clearly, any linear spatial embedding of a graph contains no local knot. By Robinson's geometric arguments in [Rb], it can be shown that every linear spatial embedding of K6 contains a pair of linked triangles, which is equivalent to the Hopf link. Also Brown [Br] proved that every linear spatial embedding of K-j contains a trefoil knot. We shall show a more general answer to our question, as follows:
Theorem 2. Given a link k, there is a finite number R(k) such that any linear spatial embedding of the complete graph Kn with n > R(k) contains a link equivalent to k.

We call such a minimum R(k) in Theorem 2 the Ramsey number of a link k with respect to equivalence and use the same notation R(k) for it. For example, R(k) = 6 for the Hopf link and R(k) = 7 for the trefoil knot by Robinson's and Brown's results, respectively. (Since any cycle consists of at least 3 edges, it is obvious that R(k) > 6 for every nontrivial link with two or more components.
License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use

RAMSEYTHEOREMS

529

Figure 1
Figure 1 shows a linear spatial embedding of K6 , ambient isotopic to the one given by Figure 1 in [CG], which contains no nontrivial knot and hence R(k) > 7 for every nontrivial knot.) The Ramsey numbers will be however very large in general. Also we can define the Ramsey number R+(k) of a link k with respect to ambient isotopy in a similar way and can show its existence, modifying slightly

the proof of Theorem 2.

Theorem 3. Given a link k, there is a finite number R+(k) such that any linear spatial embedding of the complete graph Kn with n > R+(k) contains a link ambient isotopic to k.
Let k be the mirror image of k . Then the following inequality follows from the definition of Ramsey numbers of links.

R(k) = R(k) < R+(k) = R+(k).

In particular if k is amphicheiral, that is, if k is ambient isotopic to k , then R(k) = R+(k), but this equality does not hold in general. For example, R(k) = R+(k) for the figure-eight knot k but this value is unknown. On the other hand, Figure 2 shows a linear spatial embedding of K7, ambient isotopic to the one given by Figure 7 in [CG], which contains only one nontrivial knot and the unique nontrivial knot 1234567 is equivalent to the
trefoil knot. Since the trefoil knot is not amphicheiral, any linear embedding of Kn with n > R+(k) has to contain at least two nontrivial knots, one of which is the right-handed trefoil and the other is the left-handed one. Thus, R+(k) exceeds 7 (= R(k)) and also its value is unknown for the trefoil knot k . Furthermore, we shall discuss the Ramsey number of spatial graphs and establish the most generalized version as follows.

Theorem 4. Let Gx, ... , Gs be s spatial graphs. Then there is a finite number

R(GX,... ,Gf) such that if n> R(GX,..., Gf), then any linear spatial embedding of the complete graph Kn with an arbitrary partition E(Kf = E{ U UE contains a spatial graph H with E(H) c E which is ambient isotopic to a subdivision of G for some i.

A partition of the edge set E(Kn) = Ex U U Es is often interpreted as an edge-coloring of Kn with s colors, so this theorem with s = 2 implies
License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use

530

SEIYA NEGAMI

Figure 2
that we can always find either a red Gx or a blue G2 in a sufficiently large complete graph with edges painted red and blue at random. If one omits all topological conditions and replaces "ambient isotopic" with "isomorphic", then Theorem 4 will be translated into the theorem for the generalized Ramsey number r(Gx, ... , Gf of graphs Gx, ... , Gs in the combinatorial sense. (See [BM, p. 109].) That is why we entitled this paper Ramsey theorems for... . In fact, we shall use Ramsey's original theorem [Ra], as follows, to prove Theorems 2, 3 and 4. Here we shall denote by (x) the family of /-element

subsets of X.
Theorem 5 (Ramsey [Ra]). Let t,k, ax, ... , ak be positive integers. Then there exists a finite number R(t ;k; ax, ... , ak) such that if a finite set X contains at least R(t ; k; ax, ... , ak) elements, then for any partition (f ) = Xx U- uXk of the family (*), there is an a -element subset A of X, for some i, such that

(1)CX.
This is one of the most famous theorems in combinatorics and is the starting point of what is called Ramsey theory, which has produced various results in not only combinatorics but also algebra, geometry, topological dynamics and so

on. (See [GRS] for example.) An application of Ramsey's theorem to knot theory can be found in [Mo], where Motzkin showed the existence of a bound R such that every general position set with at least R points contains a knotted polygon. (Now we know that the bound R is equal to 7 by Brown's result [Br].) He discussed the existence of a certain special position in space, using Ramsey's theorem, and found an octahedral position in a sufficiently large general position set. It is clear that any octahedral position contains a knotted hexagon, which is equivalent to the trefoil knot. The strategy of our proof in 2 also is to find such a special position that contains a given knot or link. However, our problem is not so easy since there is not an explicit model like an octahedron, and is very delicate since we have
License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use

RAMSEY THEOREMS

531

to find there an ambient isotopic image but not a rigid configuration. Then we divide the proof into four steps with local targets. We shall work in the PL category, so every embedding is a tame one and hence every spatial embedding of a graph G is isotopic to a linear spatial embedding

of a subdivision of G.
2. Proofs
Throughout this section, we shall prove Theorems 2, 3 and 4. Our proof consists of four steps with the following outline. _i_ 'i 2 1 Let T be the set of points in R with xyz-coordinates (x, x , x ) for positive real numbers x G R

r = {(x,x2,x3)GR3:x>0}.
We call T+ the positive curve and T~ the negative curve. It is well-known that every subset A on these curves T* is in general position and hence any two line segments with ends in A do not meet in their inner points. This implies that the union of line segments which join all the pairs of points in A yields a linear spatial embedding of Kn if A consists of n points. First, we construct a given link k with broken lines whose corners lie on T+ . We shall say simply that we put k on T+ , meaning this construction. In this case, the projection of such k to the xy-plane has only positive crossings (see Figure 3). So we have to discuss whether or not there is actually such a projection of k in the xy-plane, considering plat representations of k, before we put k on T+ . Next, we find the same configuration as k put on T+ in any general position set of sufficiently large size, using Ramsey's theorem. These three steps also proceed for spatial graphs with little modification. In the final step, we shall conclude the three theorems, comparing their difference. Step 1. Any spatial graph has aplat representation with only positive crossings.
Put 2 vertical lines Lx, ... , L2n of the same length on the xy-plane and join each neighboring pair L2/ , and L2i with arcs at the top and bottom so as to make n long circles, called a trivial plat representation, which presents a trivial link with n components. We give each line L the upward direction and replace several parallel parts with positive or negative crossings as given in Figure 3. (These names are contrary to the usual sense but give the consistency to our later terminology in this paper.) The resulting figure exhibits a link k in R . Then we call such a representation an n-plat representation of k . It is clear that any link has an -plat representation for some n . For spatial graphs, we modify the trivial plat representations as follows. Let dx, ... , d be positive integers which sum up to an even number 2m = dx-\-h dp . We join parallel lines Lx, ... , L2n (n > m) in pairs at their bottoms by arcs as well as for a plat representation of a link. On the other hand, we identify the top ends of d lines in order to make maximal points as vertices of degree
License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use

532

SEIYA NEGAMI

positive Figure 3

negative

d and join the remaining n - m pairs of L2m+X,... , L2n by arcs. This is a trivial plat representation of a spatial graph, which is a union of paths with selfloops and a trivial link. Adding crossings to a trivial plat representation, we get an -plat representation of a spatial graph with degree sequence (dx, ... , d ). Given a spatial graph G, move all the vertices and all the local maximal points on edges upward to the top and next move all the local minimal points to the bottom. Then an -plat representation of G as above will be obtained for some . An -plat representation is said to be positive (or negative) if it has only positive (or negative) crossings. Here we shall show that every spatial graph has a positive plat representation. Let P(G) be any plat representation of a spatial graph G. After ambient isotopic modification, we can assume that no two of crossings in P(G) lie on the same horizontal level. If P(G) includes a negative crossing, then we choose the lowest one and turn the lower part of P(G) around the vertical axis through the crossing. The number of positive crossings has increased but that of negative crossings has decreased by one in the resulting representation. In fact, one negative crossing has been replaced with precisely ( - 1)(2 + 1) positive crossings. We can eliminate all the negative crossings by repeating this process and the claim of Step 1 follows. D

Figure 4
Step 2. Any spatial graph G is ambient isotopic to a linear embedding of a subdivision of G whose vertices lie on the positive curve T+ , that is, we can put

G on T+.
License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use

RAMSEYTHEOREMS

533

plat bottoms

Figure 5
We shall construct the desired linear embedding inductively, relying upon a positive plat representation P(G) of G. Notice that the projections of two directed edges axa3 and a2a4 (ax, a2, a3,a4 e T+) cross each other in the xy-plane and their crossing is positive if and only if four points ax, a2, a3 and a4 lie on T+ in such an order that their x-coordinates increase. It is easy to put any spatial graph with a trivial plat representation on T+ . For example, Figure 5 gives the desired subdivision G+ of a graph G with a trivial 3-plat representation P(G). The original graph G has only two vertices of degree 1 and 5 while G+ has seven vertices, three and two of which correspond to the minimal and maximal points of the plat representation P(G). We call the former plat bottoms, the latter plat tops and the others intermediate vertices. Furthermore, we divide V(G+) into two classes at some height and call them the lower and upper classes, respectively, in order to describe the following construction of G+ . We choose the height for a trivial -plat representation so that the lower class consists of only all the plat bottoms and the upper class contains the other vertices including all the plat tops. In process of our construction, we will add new intermediate vertices to the lower and upper classes, depending on their height. Assume that G has a positive -plat representation P(G) and let H be the spatial graph with the positive -plat representation P(H) that is obtained from P(G) by replacing its lowest crossing with parallel vertical segments. Even if P(H) has an inessential crossing, we do not cancel such a crossing so that P(H) differs from P(G) in only one crossing at their bottoms. Thus, also P(G) is allowed to have some inessential crossing. We need this assumption to carry out our inductive construction below. By the induction hypothesis, there is a linear embedding of a subdivision H+ of H such that V(H+) c T+ and an ambient isotopy deforms it into the plat representation P(H) of H. We shall construct the desired spatial graph G+ for G from this spatial graph H+ .
License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use

534

SEIYA NEGAMI

Furthermore, we can suppose the following four conditions (i) to (iv) for H+. Let ux, ... ,un be the plat bottoms of H+ numbered so that their xcoordinates increase in this order and let ut and us be the two directed edges incident to u which go upward from u to left and right, respectively. (i) Any vertex in the lower class is lower than any vertex in the upper class

of V(H+).
(ii) The end vertex t belongs to the upper class of V(H+). (iii) If s does not belong to the upper class of V(H+), then s lies on T between u and uj+x and is incident to a vertex in the upper class of V(H+). (iv) There is an ambient isotopy {Ht: t e 1} which deforms back H+ into P(H) as follows: First push off only intermediate vertices of V(H+) slightly from T+ . Next move down those in the upper class and move up those in the lower class so as to get an isotopic image of P(H) as H+ with many crossings cancelled. In this second step, we assume that there is a small tubular neighborhood U(T+) which the isotopy keeps unchanged. Finally, arrange the plat bottoms and tops to horizontal levels and we get the precise form of P(H). (This process should be understood with the arguments below.) Let L and L , be the two strings of P(H) which the additional crossing of P(G) switches. (They are parallel vertical lines if P(H) is a trivial plat representation.) If / is an odd number, then they reach the same minimal point of P(H). In this case, we split the corresponding plat bottom u,i+x)/2 on T+ into two vertices u" and 5, in such a small neighborhood N(u(i+X),2) that no crossing change occurs in other places, and join them by a path {u", t, u , s] of length 3 with u e N(u,i+X),2), as Figure 6. (In Figure 6, / does not lie on

r+ , but it actually should.)

We regard u as a new plat bottom and add u" and 5 to the lower class as intermediate vertices while / is placed at the highest point in the new upper class as an intermediate vertex. It is obvious that the resulting graph G+ satisfies (i) to (iii). To obtain P(G) from G+, first we push up u" slightly and move /

"(z+l)/2

Figure 6
License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use

RAMSEYTHEOREMS

535

downward into N(u,+X),2). Then we can deform G+ by the isotopy {H: t e 1} for H+ , keeping the additional crossing within N(u,+Xs,f). This ambient

isotopic deformation satisfies (iv) and carries G+ to P(G). Now suppose that / is an even number. Then L and Lf+, go down to the distinct neighboring plat bottoms u = u,2 and v = u,,2s+x, respectively.
There may be several intermediate vertices of H+ between u and v on T+ . First we split u into two non-adjacent vertices u and u" and v into v and v" and next join u to v' by an edge and u" to v" by a path of length 2 via an extra top vertex /. The resulting graph G+ is a subdivision of G as a graph. (Figure 7 illustrates the above process but does not give a real picture. There may not be an intermediate vertex 5 = s,2 between u and v . In this case, u is joined directly to "2".) The top vertex / should be the highest in the upper class of V(G+) but is not a plat top. Then edges u"t and v"t pass over each crossing and u'v' passes under all the crossings on it since each edge crossing u'v' joins one intermediate vertex and another vertices higher than v . We regard u , v" as new plat bottoms and u", v as intermediate vertices in the lower class. It is clear that (i), (ii), and (iii) hold for C7+ . An ambient isotopy for G+ with (iv) can be obtained as follows. First push off all the intermediate vertices including u", v' and / from T+ . Next simplify the broken line from v" to "2" through /, u" and 5 so that afterward it joins v" directly to "2" and smooth the path from u to "3". Now the additional crossing has been settled near v" in the tubular neighborhood U(T+). Then deform it by the same isotopy as for H+ , fixing U(T+). This process carries G+ to P(G). In either case, the four conditions (i) to (iv) have been preserved. Therefore, we can get a linearly embedded graph G+ with V(G+) cF+ which is ambient isotopic to P(G) and hence to G, repeating these deformations downward. D
Step 3. For any positive integer , there is a finite number r(n) such that every general position set of at least r(n) points in R3 contains a positive or negative position subset of points.

Figure 7
License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use

536

SEIYANEGAMI

We define real numbers D4(vx ,v2,v3, vf) and D3(vx, v2, v3) for vectors v = (x, y, z) in R as the following two determinants:

x3

X,

x4-xx
y*-yi

D4(vx, v2,v3, vf = y2-yi

y^-y:

D3(vx,v2,vf

y2-yx

y3-yx

The values of D4(vx, v2, v3, vf and D3(vx, v2, vf) depend on the order of vectors v in general. Let A = [ax, ... , an) be a set of finitely many points in R3. If A has the following five properties (i) to (v) for certain right-handed (or left-handed) xyz-coordinates, then A is said to be in positive position (or negative position). (i) A is a totally ordered set in the lexicographical order with respect to xyz-coordinates. (ii) A is in general position in R3. (iii) The projection p(A) is in general position on the xy-plane R , where 3 2 p : R > R is the orthogonal projection. (iv) D4(a, j , ak , a) > 0 for any 4-element subset E = {a, a, ak, a} with a < a < ak < a. (v) D3(a, j, ak) > 0 for any 3-element subset F = {a,aj,ak} with a < j < ak . We shall often write simply DfE) and DfF) for Dfa, 3;., ak, af and D3(a, a, ak), respectively, since elements of E and F have the specified ordering under the order of A . For example, every finite set on the positive or negative curve Y is in positive or negative position, respectively. We shall show the geometric meaning of positive position in the next step and find here a positive or negative position set of arbitrary size in a sufficiently large general position set combinatorially, using Ramsey's theorem. In particular, we shall use R(4;2; N, N) and

i?(3;2;,

).

Let X be a finite general position set in R . Then we can choose a righthanded xyz-coordinate system for which p(X) is in general position on R and make X totally ordered lexicographically with respect to xyz-coordinates. Thus, every subset of X satisfies (i), (ii) and (iii) in the definition of positive and negative positions. Now we separate the family (x) of 4-element subsets of X into two classes as follows. Let E = {a, j, ak, af be any element in iff). Since X is in general position, D4(E)^0. So we set X+ and X_ to be the classes consisting of all the 4-element subsets E with D4(E) positive and negative, respectively.
License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use

RAMSEYTHEOREMS

537

Then (x4)= X+ UX_ and l+nl_=0. By Ramsey's theorem, if X contains at least R(4; 2; N, N) points, then there is an ./V-elementsubset Y in X such that either X+ or X_ contains (Y4). Let F = {a, a, ak} be any 3-element subset in Y. Then D3(F) ^ 0 by condition (iii). Thus the family (3) of 3-element subsets of Y splits into Y+ and Y_ which consist of 3-element subsets F of Y with D3(F) positive
and negative, respectively. By Ramsey's theorem again, if Y contains at least R(3; 2; , ) elements, then there is an -element subset A in Y such that either Y+ or Y_ contains (3).

Therefore, if X contains at least R(4 ; 2 ; R(3 ; 2 ; , ), R(3 ; 2 ; , )) elements, then we can find an -element subset A in X which satisfies one of the following four:

E(f '
(+-)
(-+) ()

D4(E)>0
D4(E) < 0 D4(E)<0

A\\ [Eel")) 4
A ( E e , )) [Ee (.)) 4
A\\

, ,, . and D3(F)<0
and
.

(')
(F e
(^(3))
(

(_

(A

D3(F) >0
^ twn .

(A

and D3(F)< 0

[F e

It is obvious that ^4 is in positive position if ,4 satisfies condition (++). In the other cases, we can conclude that A is in positive position (()) or negative position ((H) or (h)), by choosing x-, y- and z-axes suitably. Thus, the desired number r(n) exists and can be chosen not to exceed

R(4; 2;R(3; 2; n, ), R(3; 2; n, )).

Step 4. Conclusion.

Let G be a spatial graph and f:Km R3 any linear embedding of the complete graph Km on m vertices. The number m will be adjusted later to each theorem. We may assume that f(V(Km)) is in general position. Let G+ be the linear spatial graph constructed in Step 2, which is ambient isotopic to a subdivision of G and set = |F(C7+)| to prove Theorem 2. By the previous arguments, if m > r(n), then fi(V(Km)) contains a positive or negative position set A = {ax, ... , an) of size . When A is in positive position, we may assume that A satisfies condition (++) in Step 3 for certain right-handed xyz-coordinates and that a, < < an . Then A has the following three properties: (i) The points p(ax), ... , piaf) lie on the boundary of their convex hull Ci on the xy-plane R counterclockwise in this order. (ii) The orthogonal projection of the linear spatial complete graph over A on the xy-plane has only positive crossings.
License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use

538

SEIYANEGAMI

(iii) The projections of two directed edges aak and a-at cross each other in the xy-plane and their crossing is positive if and only if a < a < ak < a. This is the geometric meaning of positive position. If A is in negative position, then its mirror image is in the same configuration as above. Let vx, ... ,vn be the vertices of G+ which lie on T+ upward in this order. We define a bijection h : V(G+) > A by h(v) = a (i = I, ... , n) and extend it to a graph isomorphism h: G+ >H between G+ and a subgraph H in the complete graph over A. Suppose that A is in positive position. Then both spatial graphs G+ and H have projections with only positive crossings on R and two edges p(v)p(vk) and p(v)p(v) cross each other if and only if their images p(a)p(ak) and p(aj)p(af do. Therefore, C7+ and H are ambient isotopic and h extends to an orientation-preserving homeomorphism of R . On the other hand, if A is in negative position, then G+ is ambient isotopic to the mirror image of H and h extends to an orientation-reversing homeomorphism of R . This implies that R(G) < r(n). If we restrict G to be a knot or link k, then Theorem 2 will be obtained. In the same way as Step 2, we can put G on the negative curve T~ and get a linear spatial graph G~ , ambient isotopic to a subdivision of G, whose vertices lie on T~ . Now set n = max{\V(G+)\, \V(G~)\} to prove Theorem 3. If m > r(n), then there is a positive or negative position set A of points in fi(V(Km)), again. We find G+ in A when A is in positive position and G~ in A when A is in negative position. In either case, f(Km) contains a subgraph ambient isotopic to a subdivision of G, whose vertex set may not coincide with A , and hence R+(G) < r(n). Let C7* and G~ be linear spatial graphs which are ambient isotopic to
subdivisions of G and whose vertex sets are in positive and negative positions, respectively. Set n = max{\V(G*)\, \V(G~)\) to prove Theorem 4. Now we use the Ramsey number R(2; s; r(nx), ... , r(nf) and assume that m > R(2 ; s; r(nx), ... , r(nf). Then every linear embedding of Km with edges

colored by 5 colors contains a monochromatic K, , for some /' as its subgraph by Ramsey's theorem and this monochromatic Kr{n) contains a subgraph ambient isotopic to a subdivision of G. D

3. Estimation

of Ramsey numbers

In this section, we shall estimate rough bounds for the Ramsey numbers R(k) of knots and links, using the following numerical invariants. The crossing number of a link k , denoted by cr(k), is defined as the minimum number of crossings taken over all the projections of k . For example, the knot and link tables in [Ro] give us the classification of knots and links with respect to their crossing numbers. In this table, the Hopf link, trefoil knot and figure-eight knot are denoted by 2X, 3, and 4X, respectively, and these notations mean that cr(22) = 2, cr(3,) = 3, and cr(4,) = 4. Clearly, cr(0) = 0 for the trivial knot 0.
License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use

RAMSEYTHEOREMS

539

A<^
trivial tnvial trefoil ^

^"-A figure-eight

Figure 8
Here, we define the broken line number of a link k as the minimum number such that a polygonal curve or a union of polygonal curves with edges realizes k and denote it by bl(V). For example, bl(0) = 3 for the trivial knot 0 and bl(2j) = 6 since the Hopf link 2, can be realized as two linked triangles. Also we can show that bl(3) = 6 and bl(4t) = 7, classifying polygonal curves with a few edges as below.

Theorem 6. There are precisely three spatial polygons with seven edges, given by Figure 8, up to ambient isotopy preserving the linearity of edges and they are equivalent to the trivial, trefoil and figure-eight knots, respectively. In particular, the first two can be derived from a spatial hexagon.
Proof. First deform a polygonal knot k slightly so that its vertices are in general position and suppose that k cannot be obtained from a polygon with six edges by subdividing one edge and bending it. (The first two in Figure 8 are such excluded types.) Then each quadruple of vertices forms a tetrahedron and if k runs along two edges of a face of the tetrahedron, the face has to be pierced by another edge of k . Under this situation, we can construct only the third one in Figure 8 as k. It is a tedious routine to see this fact, so we shall omit it. (See [CF, p. 11, Exercise 2].) G
If a link k is contained in a linear spatial graph, then it forms a union of polygonal curves. Thus, the broken line number hl(k) is an obvious lower bound for the Ramsey number R(k). On the other hand, we can show lower and upper bounds for hl(k) in terms of the crossing number cr(k) as follows. Theorem 7. (i) If a link k is not equivalent to the trivial knot,

5 + V25 + 8(cr(fc)-2)^uu^
(ii) If a link k has neither the Hopf link as a connected sum factor nor a splittable trivial component, then

hl(k)<2cr(k).
Proof, (i) Suppose that k admits a polygonal representation Q with edges and that there is an edge e0 which does not lie on a triangle component of Q.
License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use

540

SEIYA NEGAMI

Then we move the polygon Q so that e0 stands vertically (or in parallel to the z-axis) and the others do not. Consider the orthogonal projection of Q to the xy-plane and count the number of crossings in p(Q), where p:R3-R2 is the projection map. Since the edge e0 projects to a single point, p(ef contains no crossing and p(Q) consists of - 1 edges. Each edge of p(Q) contains at most - 4 crossings since any three consecutive edges do not cross one another. Thus, p(Q) contains at most ( - 1)( - 4)/2 crossings and we have the inequality

in-l)n-4)>crjk).
Solving this, we get the first inequality in the theorem if Q has a component with at least four edges. When Q consists of only / triangles, clearly hl(k) = 3/ and any two components have at most two crossings in common. Thus,

cr(k)<t(ttrivial knot if / = 1.

1).

In this case, the inequality of (i) still holds if / > 2 and k is equivalent to the
(ii) Let G be the 4-regular graph on the xy-plane obtained from a minimumcrossing projection of k by regarding each crossing as a vertex of degree 4 and let G' be the graph obtained from G by replacing each pair of multiple edges with a single edge. Then G' is a simple graph with vertices of degree 3 and 4. (If k had a splittable trivial component, then G would have a part with no vertex and would be a graph no longer.) It is well known that every graph embedded in the plane can be represented as a graph with each edge a straight line [Fa, Sa, Wa]. In our terminology, G' is ambient isotopic to a linear embedding G" in the plane. Then split each vertex of G" into an upper and a lower point in R3 and join them by straight lines naturally corresponding to edges of G. The resulting figure forms a union of polygons Q in R which projects precisely to G" . If Q has self-intersection, then such a crossing point lies on two edges contained in one vertical plane and these edges project to an edge of G" which corresponds to a pair of multiple edges of G. We can however push them off slightly so as to eliminate the crossing and get a piecewise linear representation of k as a slightly modified Q. (Notice that no vertical plane contains three edges of Q. Otherwise, the part of k corresponding to these three edges would form a connected sum factor equivalent to the Hopf link.) Now we count the number of edges of Q which coincides with that of G.

Since G is a 4-regular graph, we have 2\E(G)\ = 4\V(G)\ and \V(G)\ = cr(k)

by the assumption of G. Thus, k can be constructed as a union of broken

lines with 2cr(k) edges and hence hl(k) < 2cr(k).

For example, the left hand of the inequality in (i) exceeds 5 if cr(A:) = 3. Thus, we can conclude that bl(3,) = 6 by only the above theorem. However, if we had never taken account of the edge e0 standing vertically, then our conclusion would be that bl(3, ) 5 or 6. If we can find many edges which can
License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use

RAMSEYTHEOREMS

541

be in parallel to one another in a polygonal representation of a link k , then the

lower bound for hl(k) will be improved.

Corollary 8. Let k be a link which has an m-plat representation with c+ positive crossings and c_ negative crossings. If k is not equivalent to the trivial knot, then we have the following inequalities:

5 +v/25 + 8(cr(/c)-2)

< R{k) ^ r{3{m + c+ + c_(m _ 1)(2w + 1))}_

Proof. The left inequality follows immediately from Theorem 7. To show the right inequality, recall the setting of in Step 4, which has been chosen to be the number of vertices of G+ with vertex set in positive position. In Step 1, we replaced each negative crossing with (m - l)(2m + 1) positive crossings, starting with a given m-plat representation of k, and get a positive m-plat representation with c+ + c_(m - l)(2m + 1) crossings. In Step 2, we made three new vertices for each positive crossing to put k on T+ , starting with a trivial m-plat representation. Such a trivial m-plat representation on T+ has precisely 3m vertices if we confine the object to a knot or link. Thus, the resulting polygonal k has at most 3(m + c+-l-c_(m-l)(2m-l-l)) vertices and this number should be chosen as the parameter in r(n). D Also we get an upper bound for R+(k) by similar arguments
R+ik) < r(3(m + max{c+ , c_) + (ml)(2m + 1) x min{c+, c_})).

This is not however so worthy since the values of the original Ramsey numbers are unknown.

References
[BM] [Br]
[CF] [CG]
[Fa]

J. A. Bondy and U. S. R. Murty, Graph theory and its application, Macmillan, 1976. A. F. Brown, Embedding of graphs in E , Ph.D. Desertation, Kent State Univ., 1977.
R. H. Crowell and R. H. Fox, Introduction to knot theory, Springer-Verlag, 1963. J. H. Conway and C. McA. Gordon, Knots and links in spatial graphs, J. Graph Theory 7

(1983), 445-453.
I. Fry, On straight line representation of planar graphs, Acta Sei. Math. (Szeged) 11 (1948),

229-233.
[GRS] R. L. Graham, B. L. Rothschild and J. H. Spencer, Ramsey theory, Wiley, 1980. [Mo] T. H. Motzkin, Cooperative classes of finite sets in one and more dimensions, J. Combin.

[Ra] [Rb] [Ro] [Sa]

Theory 3(1967), 244-251. F. P. Ramsey, On a problem of formal logic, Proc. London Math. Soc. 30 (2) (1930), 264286. D. F. Robinson, Symmetric embeddings of graphs, J. Combin. Theory 9 (1970), 377-400.
D. Rolfsen, Knots and links, Math. Lecture Series 7, Publish or Perish, 1976. H. Sachs, On a spatial analogue of Kuratowski's theorem on planar graphs2 open problem, Graph Theory, Lagw 1981, Proceedings, Lecture Notes in Math., vol. 1018, SpringerVerlag, Berlin and Heidelberg, 1983, pp. 230-241. S. K. Stein, Convex maps, Proc. Amer. Math. Soc. 2 (1951), 464-466.
K. Wagner, Bemerkungen zum Vierfarbenproblem, Jber. Deutsch. Math.-Verein. 46 (1936),

[St]
[Wa]

26-32.
Department 156 Tokiwadai, of Mathematics, Faculty of Education, Hodogaya-Ku, Yokohama 240, Japan Yokohama National University,

License or copyright restrictions may apply to redistribution; see http://www.ams.org/journal-terms-of-use