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

A short pro of of the linear Conway-Gordon-Sachs Theorem Arseny Zimin
Abstract In this paper we present a short and apparently new proof of the linear Conway-GordonSachs 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. 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 the 3-dimensional space are in general position. Then there exist two linked triangles with vertices at these points. See another proof of the Conway-Gordon-Sachs Theorem in [CG83]. That proof is based on the idea that if we move one of our six points then the parity of number of pairs of linked triangles does not change. Then one constructs an example when this number is odd. But in our proof we reduce this theorem to a result for the plane. Pro of of the linear Conway-Gordon-Sachs Theorem. To prove the linear ConwayGordon-Sachs Theorem we will use two following lemmas. To state the first lemma we need the following definition. Let a, b be segments in 3-dimensional space, S 2 be a sphere whose center is denoted by O. A segment a is lower than a segment b, if there exist a half-line with the endpoint O that intersects segment a, say at the point A, and segment b, say at the point B , A = B and A [OB ]. Analogously one can define what it means for a segment a to be higher than a segment b. Lemma 1. Assume that the vertices of two triangles are in general position. Denote by A1 A2 A3 the first triangle. Denote by S 2 a sphere with the center A1 and radius so smal l that al l the vertices of the triangles except A1 are outside S 2 . If the number of the sides of the second triangle that are lower than A2 A3 is odd then these two triangles are linked. Remark. The condition that the vertices of the triangles except A1 are outside the sphere could be avoided at the price of some complications both in the statement and the proof. Proof of Lemma 1. Denote by A4 , A5 , A6 the vertices of the second triangle. Let f : R3 - {A1 } S 2 be the central pro jection with the center A1 . For any two segments a and b that are outside the sphere S 2 we have that if a is higher than b then f (a) intersects f (b). And we have that 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 is higher than A4 A5 . Then the point f -1 (f (A2 A3 )) A4 A5 is inside the 2-dimensional triangle A1 A2 A3 . Since f (A2 A3 ) is an ark of a circle on S 2 and f (A4 A5 A6 ) is a spherical triangle on S 2 , 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 . And the vertices of these two triangles are in general position. Then these two triangles are linked. QED.


Figure 1: To Lemma 1 Lemma 2. 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. This lemma is known, see, e.g., [Sk, §1]. Proof of Lemma 2. 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 position of the first point keeping the remaining four fixed then the number v (f ) is not changed. Suppose that we change the position of point K f . Denote by K the new position of the point K and by f the obtained collection. Case 1. 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 the assertion 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 at an even number of points, see e.g. [BE]; ·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 . Case 2. Assume that points from the set f f are not in general position. 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 the Case 1 implies that v (f ) = v (f ) = v (f ). QED. Remark. There is a spherical analogue of this lemma whose proof is analogous. 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. Denote by E the set of segments joining pairs of points A2 , A3 , A4 , A5 , A6 . Consider a sphere S 2 with the center A1 . We may assume that this sphere is so small that points A2 , A3 , A4 , A5 , A6 are outside the sphere. Consider the central pro jection f : R3 - {A1 } S 2 with the center A1 . For any ordered pair (e, e ) E 2 denote 1, if e is higher than e ; e e := . 0, otherwise. For any segment e E define the number Se :=
e (E -{e})

ee.

Define v (f ) to be the sum of numbers of intersection points of segments e, e E for all unordered pairs {e, e } E of disjoint segments e, e . Then Se e e v (f ) 1 mod 2.
eE (e,e )E
2

Hence for some the 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. 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 segments e, e E do not have common endpoints and f (e) f (e ) = then e e + e e = 1 · if segments e, e E have a common point or f (e) f (e ) = then e e + e e = 0. The third equality follows from the spherical analogue of Lemma 2. 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, http://www.mccme.ru/circles/oim/algor.pdf [BE] V. Boltyansky, V. Efremovich, Visual topology, in Russian, http://ilib.mccme.ru/djvu/geometry/boltiansky-nagl-topo.htm [CG83] J. Conway and C. Gordon, Knots and links in spatial graphs , Jour. Graph Theory 7 (1983), p. 445-453.