Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/circles/oim/mmks/works2013/zimin4.pdf Дата изменения: Thu Dec 19 12:58:08 2013 Дата индексирования: Sat Mar 1 23:16:08 2014 Кодировка: Поисковые слова: images

An alternative pro of of the Conway-Gordon-Sachs Theorem Arseny Zimin
Abstract

1

In this paper we present a short and apparently new proof of the Conway-Gordon-Sachs Theorem on the complete graph on 6 vertices. We reduce this theorem to certain property of the complete graph on 5 vertices mapped to the plane.

Points in 3-dimensional space are in general position, if no four of them are in one plane. By a triangle we always mean a 2-dimensional triangle, i.e. the convex hull of three general position points. Two triangles in 3-dimensional space whose six vertices are in general position are linked, if the outline of the first triangle intersects the interior of the second triangle exactly at one point. Linear Conway-Gordon-Sachs Theorem. Assume that six points in 3-dimensional space are in general position. Then there exist two linked triangles with the vertices at these points. Consider a closed broken line a in 3-dimensional space. A finite set of triangles in 3-dimensional space is called a membrane spanned on a, if the following conditions hold: · Any side of a is a side of exactly one triangle from this set; · Any side of a triangle from this set that is not a side of a belongs to exactly two triangles from this set. Two disjoint non-self-intersecting closed broken lines a and b in 3-dimensional space are linked, if there exists a membrane, denote it by A, spanned on a such that · b do not intersect the outline of any triangle from A and no vertex of b belongs to some triangle from A; · the number of triangles from A that intersect b is odd. Denote by Kn the complete graph on n vertices. Conway-Gordon-Sachs Theorem. Assume that the graph K6 is piecewise-linearly embedded in 3-dimensional space. Then there exist two linked cycles of length 3 in this graph. Remark. The statement of the theorem is meaningful because any cycle of length 3 in this graph is a closed broken line. The original proof of the Conway-Gordon-Sachs Theorem [CG83] has two steps. In the first step it is proved that change of our six points does not change the parity of number of pairs of linked triangles.2 In the second step one constructs an example when this number is odd. Our proof is by reduction to a result for the plane. That result is proved in analogous two steps. They are easier, in particular, construction of planar example rather than spatial example is much easier. The main idea of our proof is shown on page 4 for the linear case and on page 6 for the piecewise-linear.
This paper is prepared under the supervision of Arkady Skopenkov and Mikhail Skopenkov and is submitted to the Moscow Mathematical Conference for High-School Students. Readers are invited to send their remarks and reports on this paper to mmks@mccme.ru 2 The proof of the first step uses either one of the following two facts: (1) any broken line and 2-dimensional sphere that are in general position intersect in an even number of points; (2) any two piecewise-linear embeddings of the graph K6 in 3-dimensional space are related by isotopy and crossing changes where edges are allowed to pass through each other.
1

1


Figure 1: To Lemma 1 There is a shorter unpublished proof of the linear case invented by Alexander Shapovalov. That proof does not generalize to the proof of the piecewise-linear case. Pro of of the linear Conway-Gordon-Sachs Theorem. In the proof we use the following definition and well-known lemmas whose proofs are presented by completeness. Definition of the notions of being higher and lower. Let a, b be segments in 3-dimensional space, be a plane such that segments a, b are in one half-space with respect to and O be a point in other half-space with respect to . A segment a is lower than a segment b with respect to plane and point O, if there exists a half-line OX with the endpoint O that intersects segment a at a point A := a OX , and segment b at a point B := b OX , so that A = B and A is in the segment OB . Analogously one can define the notion of a segment a being higher than a segment b. Lemma 1 (see Figure 1). Assume that the vertices of two triangles are in general position. Denote by A1 A2 A3 the first triangle. We may assume that A1 is the unique point among them whose first coordinate a is maximal. Consider a plane x = b, denote it by , where b is slightly smal ler than a. If the number of the sides of the second triangle that are lower than A2 A3 with respect to plane and point A1 is odd then these two triangles are linked. Proof of Lemma 1. Denote by A4 , A5 , A6 the vertices of the second triangle. We will say that point A1 is in first half-space with respect to and points A2 , ..., A6 are in second half-space with respect to . Let f : R3 - {A1 } be the central pro jection with the center A1 . For any two segments a and b that are in second half-space with respect to , if a is higher than b then f (a) intersects f (b). Moreover, if f (a) intersects f (b) then a is higher than b or b is higher than a. By the assumption of the lemma there exists a side, say, A4 A5 , of the triangle A4 A5 A6 such that A2 A3 2


is higher than A4 A5 . Then the point f -1 (f (A2 A3 )) A4 A5 is in the interior of the triangle A1 A2 A3 . Since f (A2 A3 ) is a segment in and f (A4 A5 A6 ) is a triangle in , f (A2 A3 ) intersects the outline of f (A4 A5 A6 ) in at most 2 points. So A4 A5 is the unique side of the triangle A4 A5 A6 that is lower than A2 A3 . This implies that the outline of the triangle A4 A5 A6 intersects the interior of the triangle A1 A2 A3 at a unique point f -1 (f (A2 A3 )) A4 A5 . Since the vertices of these two triangles are in general position it follows that these two triangles are linked. QED. Consider a set A of points in the plane. We will say that the set A is in general position in the plane, if the following conditions hold: · no three points from A lie on one line; · no three segments joining some three pairs of points from A have a common point. Lemma 2. [Sk] Let a col lection f of five points in general position in the plane be given. Then the sum of numbers of intersection points of the segments AB and C D for al l unordered pairs {{A, B }, {C, D}} of disjoint two-element subsets {A, B }, {C, D} f is odd. Proof . For any four distinct points A, B , C, D of the collection f , the segments AB and C D either are disjoint or have a unique common point. Define v (f ) to be the parity of the sum of numbers of intersection points of the segments AB and C D for all unordered pairs {{A, B }, {C, D}} of disjoint two-element subsets {A, B }, {C, D} f . f , {A, B } {C, D} = } mod 2. 2

v (f ) :=

{|AB C D| : {{A, B }, {C, D}}

This lemma is implied by the following two assertions. (a) For the collection f0 of five vertices of a regular pentagon we have v (f0 ) = 1. (b) v (f ) does not depend on f . Assertion (a) is clear. Let us prove (b). It suffices to prove that if we change the first point keeping the remaining four fixed then the number v (f ) is not changed. Suppose that we change point K f to K . Denote by f the obtained collection. There exists a point K such that points from each of two sets {K } f and {K } f are in general position. Denote f := (f - {K }) {K }. Then it suffices to prove that v (f ) = v (f ) and v (f ) = v (f ). So it suffices to prove the item (b) for the case when points from the set f f are in general position. Assume that the points from the set f f are in general position. For each A f - {K } denote by A the triangle with vertices from f - {A, K }. Then assertion (b) follows from v (f ) - v (f ) = (|K A
Af -{K } A

| - |K A

A

|) =
Af -{K }

|K K

A

| = 0 mod 2.

· Here the first equality is clear. · The second equality holds because |K K A A | is even for each A f - {K } because the outlines of two triangles on the plane whose vertices are in general position intersect each other in an even number of points, see, e.g., [BE82]. · The last equality holds because for each unordered pair {A, B } f - {K } there exist exactly two triangles with vertices from f - {K } containing the segment AB . So for each unordered pair {A, B } f - {K } the number |K K AB | appears in the sum twice for two triangles A , B . QED. 3


Deduction of the linear Conway-Gordon-Sachs Theorem from Lemma 1 and Lemma 2. Suppose that points A1 , A2 , A3 , A4 , A5 , A6 are in general position in 3-dimensional space. We may assume that A1 is the unique point among them whose first coordinate a is maximal. Consider a plane x = b, where b is slightly smaller than a. Denote by E the set of segments joining pairs of points A2 , A3 , A4 , A5 , A6 . Consider the central pro jection f : R3 - {A1 } with the center A1 . For any ordered pair (e, e ) E 2 denote lk (e, e ) := 1, if e is higher than e with respect to plane and point A1 ; . 0, otherwise.

For any segment e E define the number Se :=
e (E -{e})

lk (e, e ).

For any segment e from of numbers of intersection p disjoint segments e, e . Since e, e from E we have |f (e) Then

E we have that f (e) is a segment in . Define v (f ) to be the sum oints of segments f (e) snd f (e ) for all unordered pairs {e, e } E of our six points are in general position it follows that for any two segments f (e )| 1. So the number v (f ) is well-defined. Se lk (e, e ) v (f ) 1 mod 2.
(e,e )E
2

eE

Here the first equality follows from definition of Se . The second equality holds because · for any two segments e, e E we have |f (e) f (e )| 1 because our six points are in general position; · if the segments e, e E do not have common endpoints and f (e) f (e ) = then lk (e, e ) + lk (e , e) = 1; · if the segments e, e E have a common endpoint or f (e) f (e ) = then lk (e, e ) + lk (e , e) = 0. The third equality follows from Lemma 2. Hence for some segment from E , say, A2 A3 , the number SA2 A3 is odd. Then Lemma 1 implies that triangles A1 A2 A3 and A4 A5 A6 are linked. QED. Pro of of the Conway-Gordon-Sachs Theorem. In the proof we use the following definitions and well-known lemmas whose proofs are presented by completeness. Consider a finite set A in 3-dimensional space. A plane is in general position with respect to A, if · the set of images of points from A under the orthogonal pro jection to the plane are in general position in the plane ; · all points from A are in one half-space with respect to . Lemma 3. For any finite set of points in 3-dimensional space there exists a plane in general position with respect to this set of points. This lemma follows from Sard's Theorem. We do not give the proof of this lemma here. Consider two segments in 3-dimensional space and a plane in general position with respect to the set of endpoints of these segments. Define what it means for the first segment to be higher than 4


the second segment analogously to the definition of notion higher that is given above but replacing 'central pro jection' with 'orthogonal pro jection'. Let A, B be two broken lines (not necessarily closed) in 3-dimensional space. Consider a plane in general position with respect to the set of vertices of these broken lines. Denote by lk (A, B ) the number of ordered pairs (a, b) of sides a of A and b of B such that a is higher than b. The number lk (A, B ) depends on the choice of plane but omit this in the notation. Two broken lines in the plane are in general position, if the union of vertices of these broken lines is in general position. For any graph G denote by V (G) the set of vertices of G and by E (G) the set of edges of G. Proof of the Conway-Gordon-Sachs Theorem. Edges of the graph K6 piecewise-linearly embedded in R3 are broken lines in 3-dimensional space. No two of these broken lines have a common interior point. By Lemma 3 there exists a plane in general position with respect to the set of vertices of broken lines that are edges of the graph K6 . Denote by a one of the vertices of the graph K6 . Consider the graph K5 = K6 - a and the orthogonal pro jection f : K5 . By the choice of the plane for any two edges e, e of the graph K5 broken lines f (e), f (e ) are in general position in . Define v (f ) to be the sum of numbers of intersection points of broken lines f (e) and f (e ) for all unordered pairs {e, e } of disjoint edges e, e E (K5 ). By the choice of the number v (f ) is well-defined. For any two distinct vertices a, b of the graph K6 denote by ab the edge of the graph K6 that contains vertices a, b. For any three distinct vertices a, b, c of the graph K6 denote by abc the cycle of length 3 in the graph K6 that contains vertices a, b, c. Denote by Cij the cycle in the graph K5 on three vertices other than i and j . We have lk (abc, Cbc )
bcE (K5 ) bcE (K5 )

(lk (ab, Cbc ) + lk (ac, Cbc )) +
bcE (K5 )

lk (bc, Cbc )


bcE (K5 )

lk (bc, Cbc ) v (f ) 1 mod 2

· The first equality is clear. · Let us prove the second equality. We have lk (ab, Cbc ) =
eE (Cbc )

lk (ab, e). For each vertex b of

the graph K5 and for each edge e of the graph K5 - b there exist exactly two those cycles of length 3 in the graph K5 - b that contain the edge e. Then each of two numbers lk (ab, e), lk (ac, e) appears twice in the sum (lk (ab, Cbc ) + lk (ac, Cbc )). Therefore this sum is even.
bcE (K5 )

· The proof of the third equality is the same as the proof of the second equality in the proof of the linear Conway-Gordon-Sachs Theorem. · The last equality follows from Lemma 5 below because for any two edges e, e of the graph K5 broken lines f (e), f (e ) are in general position in . Hence for some edge bc of the graph K5 the number lk (abc, Cbc ) is equal to 1 and Lemma 4 below implies that cycles abc and Cbc are linked. QED. Lemma 4. Let A and B be two closed broken lines in 3-dimensional space. Consider a plane in general position with respect to the set of vertices of these broken lines. If the number lk (A, B ) is odd then broken lines A and B are linked. This lemma a generalization of Lemma 1. We do not prove it here.

5


Lemma 5. [Sk] Consider a plane and a piecewise-linear map f : K5 . Assume that for any two edges e, e of the graph K5 broken lines f (e), f (e ) are in general position. Then the sum of numbers of intersection points of broken lines f (e) and f (e ) for al l unordered pairs {e, e } of disjoint edges e, e E (K5 ) is odd. This lemma is a generalization of Lemma 2. Prop osition (BE82, §1). Any two closed broken lines that are in general position in the plane intersect each other in an even number of points. Deduction of Lemma 5 from Proposition. For any piecewise-linear map f : K5 that satisfies the hypothesis define v (f ) to be the sum of numbers of intersection points of broken lines f (e) and f (e ) for all unordered pairs {e, e } of disjoint edges e, e E (K5 ). Since for any two edges e, e of the graph K5 broken lines f (e), f (e ) are in general position, the number of intersection points of these broken lines is finite. So the number v (f ) is well-defined. This lemma is implied by the following two assertions. (a) For the collection f0 of five vertices of a regular pentagon we have v (f0 ) 1 mod 2. (b) The parity of the number v (f ) does not depend on f . Assertion (a) is clear. Let us prove (b). Assume that f , f : K5 are piecewise-linear maps that satisfy the hypothesis. It suffices to prove that if these maps are equal at some subgraph K4 of our graph then v (f ) v (f ) mod 2. Indeed, if we prove this assertion it means that if we change the map f at one edge or one vertex and edges incident to this vertex so that the map f would still satisfy the hypohesis the number v (f ) does not change. Suppose that piecewise-linear maps f , f : K5 satisfy the hypothesis and they are equal at a subgraph K4 of the graph K5 . Suppose that the vertex v is not from K4 . For any vertex i of the graph K4 denote by i the cycle in K4 on three vertices other than i. For any two vertices a, b of the graph K5 denote by ab the edge of K5 containing vertices a, b. There exists a map f : K5 such that · f : K5 differs with f : K5 exactly at interiors of those edges v i, where i is a vertex of K4 , that f (v i) = f (v i); · if f (v i) = f (v i) then any intersection point of broken lines f (e) and f (e) does not lie on f ( i ). For any vertex i of the graph K4 broken lines f (v i) f (v i) and f ( i ) are in general position and then Proposition implies that these broken lines intersect in an even number of points. There exists broken line with endpoints f (v ) and f (v ) that is in general position with f (ab) and f (ab) for any edge ab of the graph K5 . Now it suffices to prove that v (f ) v (f ) mod 2 and v (f ) v (f ) mod 2. The proof of this fact is the same as the proof of Lemma 2. But one should replace 'segment' with 'broken line' and use Proposition instead of the fact that any two triangles whose vertices are in general position in the plane intersect in an even number of points. QED. The author is grateful to Arkady Skopenkov and Mikhail Skopenkov for productive discussions.

References
[Sk] A. Skopenkov. Algorithms for recognition of the realizability of hypergraphs, in Russian. See http://www.mccme.ru/circles/oim/algor.pdf.

[BE82] V.G. Boltyansky and V.A. Efremovich. Visual topology, Moscow: Nauka, 1982.

6


[CG83] J. Conway and C. Gordon. Knots and links in spatial graphs , Jour. Graph Theory 7 (1983), p. 445-453.

7