2016

2016

1 G x x G d G (x) 1 ( ) G d G (x) = 2 E(G). x V (G) 2 ( ) 1.1 1: n m on-off ( 1 ) off on 1: on-off ( on ) G v v N(v) on-off G S V (G) N(v) S { 3 G v S v S G G = 1 OK ( ) G 2 3.1 u S u u u 1

G u S u S u G u S u G S u u 3.2 u, v (u v) S u,v u v 3.1 S u S v S u,v G S u S v u v G v v v off {v V (G) : d G (v) } v 1, v 2,..., v 2k 3.2 S v1,v 2, S v3,v 4,..., S v2k 1,v 2k on 1 3 3 on-off 3 4? 2 1 on off on 1.2 2: A B 1 0m A B ( 2 2 3 B ) A B A B A B A B 2: A, B 4 A, B 2

0, 1, 2,..., l A 0 B l S = { (i, j) : 0 i j l, i j } S S (i, j) (i, j ) i = i ± 1 j = j ± 1 G S A B A i B j A i B j (i, j) (i, j ) ( ) 4.1 (i) (0, l) S G 1 (ii) (i, j) S {(0, l)} i j (i, j) G 4.1 (i) (0, l) G (0, l) C C (0, l) (i, j) 4.1 (ii) i = j C (0, l) (i, i) i A B 3 4.1 4 4 1.3 3: 5 ABCD ( 3 ) ABCD A, B, C, D A B x D y G G (x, y) x y (x, y) 4 (1, 1/2), ( 2, 1/2), ( 2, 5/2) (1, 5/2) 4 G B x D y 3

D C (1, 5/2) ( 2, 5/2) (1, 1/2) ( 2, 1/2) A B 4: G 3: 5 G 5 6 5 3? 1.4 4: Hex G a, b, c, d A B A B a, c b, d A a c B b d d c d c a b a b 5: Hex A 6: H Ã B G C 6 a, c- b, d- Ã, B, C 4

à = {x V (G) : x a }, B = {x V (G) : x b }, C = V (G) à B. a à b B c, d C 3 Ã, B, C 3 6.1 G 3 6.1 G 3 xyz x Ã, y B, z C Ã, B G a, x- b, y- z a x z b y z z C 6.1 H V (H) = { } { }, E(H) = {uv : u v à B }. H (i) 0, 1 2 (ii) 1 3 (iii) 1 (iii) H (i) (ii) 3 7 6 6-grid 1.5 5: Sperner ABC ( 7 ) ABC Sperner A 1 B 2 C 3 AB 1 2 BC 2 3 CA 3 1 1, 2 3 5

A 1 1 2 1 1 3 B 2 2 3 2 3 7: Sperner 3 C 7 (Sperner ) Sperner ABC 1, 2, 3 3 ( ) 8 7 H 6 8 (Brouwer ) f 2 f ( x f(x) = x ) 2 T = ABC x T f(x) x T 0, T 1,... 0 ( 8 ) T 0 = T k 0 T k ( 9 ) A A A B C B T 0 = T C B T 1 T 2 8: 0 T 0, T 1, T 2,... C A 1 B 2 C 3 x xf(x) T k AB 3 BC 1 CA 2 xf(x) T k A 2 3 B C 1 3 1 2 6

AB BC CA x f(x) ; X, Y {A, B, C} x XY xf(x) X x Y T k Sperner Sperner T k 3 3 i (i {1, 2, 3}) v i k A x B f(x) C 9: x f(x) x 3 T k T ( ) vk 1 ( ) u 1 k 1 l l 1 u 1 l u (as l + ) T 0, T 1,... 0 u 1 l v2 k, v3 k u2 l, u3 l u1 l u2 l, u1 l u3 l 0 (as l + ) u 2 l u, u 3 l u (as l + ) l 1 T l u 1 l 1 u1 l f(u1 l ) BC f u 1 l u (as l + ) uf(u) BC u 2 l u3 l uf(u) CA, AB 7

2 Ramsey K n n K 2 K 3 2 G H G H (2 ) Ramsey r 2 (G, H) r 2 (G, H) N K N 2 G H 2.1 Ramsey Ramsey G K n H K m 9 (1) r 2 (K 2, K m ) = m. (2) r 2 (K 3, K 3 ) = 6. (1) (a) ( ) K m 2 K 2 K m ( K m K 2 ) (b) ( ) K m 1 2 K 2 K m ( ) (2) ( ) K 6 2 v v 5 v (a) 3 (b) 3 (a) A v A v K 3 A A 3 K 3 K 3 K 3 ( ) K 5 K 3 K 3 ( ). K 6 K 3 ( 6 3) = 20 R: K 3, B: K 3, M: 2 K 3 R + B + M = 20 2 K 3 2 ( ) = 2M 8

v v r(v), b(v) r(v) + b(v) = 5 (v ) = r(v) b(v) ( r(v) + b(v) 2 ) 2 = 25 4 6 K 6 6 ( ) 36 M 18 R + B 2 9 K 7 2 K 3 4 N 7 K N 2 K 3 10 (Ramsey, 1930) n, m 2 r 2 (K n, K m ) r 2 (K n, K m ) r 2 (K n 1, K m ) + r 2 (K n, K m 1 ). N = r 2 (K n 1, K m ) + r 2 (K n, K m 1 ) K N 2 v A = {u V (K N ) : uv }, B = {u V (K N ) : uv }, A + B = N 1 (a) A r 2 (K n 1, K m ) (b) B r 2 (K n, K m 1 ) (a) r 2 (K n 1, K m ) A K n 1 K m v K n K m (b) K n K m 10 (b) 10 ( ) m + n 2 r 2 (K n, K m ). m 1 r 2 (K m, K m ) 2 2m 3 Ramsey n, m r 2 (K 4, K 4 ) = 18 43 r 2 (K 5, K 5 ) 49 10 r 2 (K 3, K 4 ) 10 r 2 (K 3, K 4 ) = 9 11 r 2 (K 3, K 4 ) 9 9

11 n, p, q 2 m = p + q 1 r 2 (K n, K m ) r 2 (K n, K p ) + r 2 (K n, K q ) 1. N 1 = r 2 (K n, K p ) 1, N 2 = r 2 (K n, K q ) 1 N = N 1 + N 2 K N K n K m K n K p K N1 K n K q K N2 K N N 1 N 2 K N1 K N2 12 K N1 K N2 r 2 (K 3, K 4 ) 8 13 r 2 (K 3, K 4 ) 9 12 (Erdős, 1947) m 3 r 2 (K m, K m ) 2 m/2. 9 (2) r 2 (K 3, K 3 ) = 6 2 2 = 2 3/2 m 4 N < 2 m/2 K N 2 K m K m N 1, 2,..., N K N 2 G N G N = 2 (N 2) K N N m m K m 2 (N 2) ( m 2) KN 2 K m GN red K m ( N m) K m 2 (N 2) ( m 2) G red N ( N m) 2 ( N 2) ( m 2) ( N m) N m ( 14) N < 2 m/2 m 4 2 m 1 G red N G N ( ) N 2 (m 2) N m m 2 2) m 2 m 1 2 (m < 2 2 (m 2) m+1 = 2 m 2 +1 1 2 K N 2 K m GN blue GN blue < 1 G N 2 ( ) G N GN red Gblue N K m K m 14 ( ) N m N m 2 m 1 12 m N = 2 m/2 1 K N K m 10

2.2 Ramsey G, H Ramsey P m m ( m 1 ) C m m 13 (Parsons, 1973) n 2 r 2 (K n, P m ) = (n 1)(m 1) + 1. ( ). N = (n 1)(m 1) K N 2 K n P m K N (m 1) (n 1) m 1 P m. n n 1 n 2 2 K n ( ) 14 m 1 m 14 ( ). n N = (n 1)(m 1) + 1 K N 2 K n P m n = 2 n 3 15 n = 2 1 x x (n 2)(m 1) + 1 x A A (n 2)(m 1)+1 A (a) K n 1 (b) P m (a) K n 1 x K N K n (b) P m 2 x x (n 2)(m 1) H V (H) = V (K N ) E(H) = {uv : uv }. 2 δ(h) N 1 (n 2)(m 1) = m 1 14 H P m K N P m 14 16 11

15 m H δ(h) m 1 H T 16 (Chvátal, 1977) T m n 2 r 2 (K n, T ) = (n 1)(m 1) + 1. 15 m 16 C m m m 4 17 r 2 (K 3, C m ) = 2m 1. 17 n 3 n H δ(h) > n/2 3 k n H k 2.3 Ramsey k 2 n 1,..., n k 2 r k (K n1,..., K nk ) N K N 1, 2,..., k i K ni r k (K 3,..., K 3 ) r k (3) 18 k 2 r k (3) k = 2 r 2 (3) = r 2 (K 3, K 3 ) = 6 r k (3) k r k (3) r 2 (K 3, K m ) m = r k 1 (3). N = r 2 (K 3, K m ) K N 1,..., k k K 3 A = 1, B = 2,..., k, K N A, B 2 N = r 2 (K 3, K m ) K N (a) A K 3 (b) B K m (a) 1 K 3 (b) K m 2,..., k k 1 m = r k 1 (3) K m K 3 17 k 4 r k (3) r 2 (K m, K m ) m = r k/2 (3) 18 r 3 (K 3, K 3, K 3 ) 17 12

2.4 Ramsey Schur {1, 2,..., 13} 3 A 1 = {1, 4, 10, 13}, A 2 = {2, 3, 11, 12}, A 3 = {5, 6, 7, 8, 9}. i (1 i 3) x, y A i x + y A i (x = y x A i 2x A i ) Schur 19 (Schur, 1916) k 1 N {1, 2,..., N} k A 1,..., A k i (1 i k) x, y A i x + y A i ( x = y ) N = r k (3) = r k (K 3, K 3,..., K 3 ) 18 N {1, 2,..., N} k A 1,..., A k i (1 i k) x, y A i x + y A i V (K N ) = {1, 2,..., N} N K N ij i j A l l K N k N = r k (3) K 3 i (1 i k) a, b, c V (K N ) ab, bc, ac i a < b < c b a, c b, c a A i x = b a y = c b x, y A i x + y = c a A i 19 k = 2 N = 5 N = 4 k G r k (G, G,..., G) k 1 N {1, 2,..., N} k A 1,..., A k i (1 i k) x, y, z A i x + y + z A i 20 (Schur, 1916) k 1 N p N p x, y, z x k + y k z k (mod p). k 1 19 N p N p x, y, z Z p Z p {0} p Z p g x Z p r x g r (mod p) 0 i k 1 i A i := {x Z p : x g r (mod p) j r = kj + i} A 0,..., A k 1 {1, 2,..., p 1} 13

N, p i (0 i k 1) x, y, z A i x + y = z x, y, z A i j 1, j 2, j 3 x g kj 1+i, y g kj 2+i, z g kj 3+i (mod p) x + y = z g kj 1+i + g kj 2+i g kj 3+i (mod p), g i (g kj 1 + g kj 2 g ) kj 3 0 (mod p) p g i 0 (mod p) g kj 1 + g kj 2 g kj 3 (mod p), x = g j 1, y = g j 2, z = g j 3 x, y, z 2.5 Ramsey K N A B A B A K m B K m A K m K m -Ramsey 21 m N K N K m -Ramsey A N = r 2 (K m, K m ) A (i) m = 3, N = 5 A (ii) m = 3, N = 4? (iii) A A (iv) m B N (N = 2m 4 ) 22 (Erdős & Selfridge, 1973) m N l = ( m 2 ) 1 l 2 l > ( N m) KN K m -Ramsey B m, N m ( 1 + o(1) ) 2 log N log 2 14

3 3.1 1-10 1 2 1 8 8 ( ) 5 6 10: 11: 5 5 23 (1) 5 5 ( 11) (2) 4 4 (1) 5 5 12 13 ( ) 4 3 2 1 a b c d 1 2 4 3 2 1 a b c d 3 5 4 5 5 1 5 2 12: b2 c3 13: b2, c2, b3, c3 (2) 12 2 b2 c3 2 1 a4 2 d1 1 2 15

2 1 a4 2 d1 3 2 23 (2) ( 2) 13 4 b2, c2, b3, c3 a1, d1, a4, d4 5 4 b1, d2, a3, c4 4 13 4 c1, a2, d3, b4 4 a1, d1, a4, d4 b1, d2, a3, c4 c1, a2, d3, b4 4 6 ( ) 4 3 2 1 a b c d c1 d3 a1 a2 c2 b4 a4 b3 c3 b2 d4 b1 a3 d1 14: (4 4)- d2 c4 15: 1-14 4 4 24 S G S G S ω(g S) S S ω(g S) S + 1 G 1-24 1-1- G S ω(g S) > S G S G S G S S ω(g S) 16

S ω(g S) > S G 24 15 1-19 24 1-25 (Schwenk) m n m n (I) m n (II) m = 1, 2 4 (III) m = 3 n = 4, 6 8 25 25 (III) m = 3 n = 8 1-1- 23 (1) (I) (II) m = 4 n = 4 23 (2) (II) m = 1, 2 20 (3 4)- (3 6)- n 5 (4 n)- 1-21 (3 8)- 1-25 3.2 3-26 (Smith, 1946 ) G 3- e G e G 17

e e e 16: 3- ( ) e 2 ( ) Thomassen e 0 OK e e = xy G = G y H V (H) = {P : P x G }, P P P = v 1, v 2,..., v n 1 ( v 1 = x) k (1 k n 3) v k N(v n 1 ) P = v 1, v 2,..., v k, v n 1, v n 2,..., v k+1 H ( 17 ) P P v 1 v k v k+1 v n 2 v n 1 v 1 v k v k+1 v n 2 v n 1 17: H G P P 26.1 P = v 1,..., v n 1 { 2 vn 1 N G (y), d H (P ) = 1 v n 1 N G (y). v n 1 N G (y), G 3- v n 1 v n 2 2 H P d H (P ) = 2 v n 1 N G (y) P = v 1,..., v n 1 v n 1 N G (y) v 1,..., v n 1, y, x G e G e y v n 1 N G (y) x v n 1 G 26.1 H 1 G e H 26 G x G x G 3- G 3 18

4 27 (, 1750?) G F (G) G V (G) E(G) + F (G) = 2. 4.1 Thurston G x (x ) +1 1 ( ) = V (G) E(G). ( ) x well-defined f f f (f ) f 1 f f f +1 ( ) = ( F (G) 1 ) + 1 = F (G) + 2 +1 1 1 +1 1 1 +1 1 +1 1 1 1 +1 +1 18: 27 ( ) 28 G ( ) G n G 2n 4 19

22 28 +2 v v d G (v) f f d G (f) ( ) d G (v) = 2 E(G) v V (G) d G (f) = 2 E(G) f F (G) ( ) d G (v) 6 + v V (G) f F (G) ( ) 2d G (f) 6 = 12 (1) 23 (1) G 2 f d G (f) 3 2d G (f) 6 0 (1) ( ) d G (v) 6 12 v V (G) 0 v d G (v) 6 < 0 29 5 30 6 (1) 29 6 4 (4 ) (1) 4 31 G G 5 G xy x 5 y 6 20

v f ( ) ch(v) ch(f) ch(v) = d G (v) 6, ch(f) = 2d G (f) 6 = 0. (1) ch(x) = 12. v V (G) 7 v 5 1/5 v ch (v) v G 5 ch(v) 1 v 5 v 7 ch (v) ( d G (v) 6 ) + 1 5 5 = 0 v 5 ch (v) ch(v) = d G (v) 6 = 0 v 7 G v 5 d G (v) 2 ( v 5 ) ch (v) ( d G (v) 6 ) 1 5 d G (v) 2 9 10 d G(v) 6 0 ch (v) 0 v V (G) ch(x) = 12 32 ( ) 3 ( ) 4 11 32 33 29 30 33 33 ( ) 2 ( ) G 3 31 ch(v) = d G (v) 6, ch(f) = 2d G (f) 6, 21

f 19 3/2 x ch (x) ch (x) = ch(x) = 12 (2) x V (G) F (G) x V (G) F (G) f 19: ( 3/2 ) 24 v f ch 0 x ch (x) 0 ch (x) 0 x V (G) F (G) (2) 33 32 ( ) 4 7 ( ) 11 5 Steinberg 4 6 4.2 34 ( ) 4- ( ) (I) 20 35 G (I) G 4-22

(II) G 3 3 (Grünbaum ) (III) G +1 1 mod 3 0 (Heawood ) 1 2 3 4 1 3 1 2 2 1 3 1 2 3 +1 +1 +1 1 1 1 20: 4- Grünbaum Heawood (I) (II) G 4- c Z 2 Z 2 4 (0, 0), (0, 1), (1, 0), (1, 1) e = xy e c(x) + c(y) + Z 2 Z 2 G 3 x, y, z 3 c(x) + c(y), c(y) + c(z), c(x) + c(z) c G c(x) c(y) c(x) + c(y) (0, 0) c(x) + c(z) c(y) + c(z) (0, 0) G Grünbaum 25 21 G (1) 4- (2) 35 (I) (II) 4- Grünbaum (3) 35 (II) (III) Grünbaum Heawood (II) (III) G Grünbaum f f 3 0, 1, 2 G T 0, 1, 2 φ : F (G) {+1, 1} T +1 1 +1 1 Heawood v v e 1, e 2,... e k e i e i+1 T i ( e k+1 = e 1 ) φ f(e i+1 ) f(e i ) φ(t i ) (mod 3) 23

+ + + + + 21: 22: f(e k+1 ) f(e k ) φ(t k ) f(e 1 ) k φ(t i ) (mod 3) i=1 f(e k+1 ) = f(e 1 ) (II) (I) G Grünbaum f f 3 Z 2 Z 2 (0, 1), (1, 0), (1, 1) ( ) 35.1 G C f(e) = (0, 0). e E(C) G c G v 0 (0, 0) v 0 (I) (II) v u c(v) = c(u) + f(uv) ( 23 ) + Z 2 Z 2 f Z 2 Z 2 4 c 2 xy c(x) c(y) xy c(x) = c(y) c x 0, x 1,..., x p ( x 0 = v 0 x p = x) x x i+1 x i c(x i ) c(x i+1 ) = c(x i ) + f(x i x i+1 ) i = 0, 1,..., p 1 i p 1 c(x) = c(x i ) + f(x j x j+1 ) (3) j=i 24

(1, 1) (1, 0) (1, 0) (1, 1) (1, 1) (0, 1) (0, 1) (1, 1) (0, 1) v 0 (1, 0) (0, 0) (1, 0) 23: Grünbaum 4- ( c ) y y 0, y 1,..., y q ( y 0 = v 0 y q = y) q 1 c(y) = c(y i ) + f(y j y j+1 ) (4) j=i i x s = y s s 0 x 0 = y 0 = v 0 s (3) (4) p 1 q 1 c(x s ) + f(x j x j+1 ) = c(x) = c(y) = c(y s ) + f(y j y j+1 ) j=s j=s p 1 q 1 f(x j x j+1 ) + f(y j y j+1 ) = (0, 0) j=s j=s (x s = y s f(y j y j+1 ) = f(y j y j+1 ) ) C = x s, x s+1,..., x p, y q, y q 1,..., y s+1, y s 35.1 e E(C) f(e) = (0, 0) (0, 0) = e E(C) p 1 q 1 f(e) = f(x j x j+1 ) + f(y j y j+1 ) + f(xy) j=s f(xy) = (0, 0) c G 4-26 35.1 C F (int(c)) 2 j=s T F (int(c)) e E(T ) f(e) 25

(III) (II) Heawood φ G e e f(e) 0 e φ(t ) = +1 T 0, 1, 2 Grünbaum (II) (I) (III) (II) 27 22 G Heawood (1) 35 (III) (II) Heawood Grünbaum (2) 35 (II) (I) Grünbaum 4-4.3 Sprouts Sprouts n A B (i) 2 ( ) (ii) (i) 4 ( 24 ) A B A B 24: n = 3 Sprouts 36 n Sprouts 3n 1 ( ) x a(x) = 3 ( ) a(x) x 3n (i) 2 (ii) 1 1 1 ( x a(x) = 1 ) 3n 1 37 n Sprouts 2n 26

n Sprouts p n + p 2 x (1) 2 (2) x N(x) 3 ( (1) ) x y N(x) N(y) n + p s 3s n + p 3s 36 s 3n p = s s p 2n 36 37 Sprouts p A B 2n ( ) 3n 1 ( ) (n = 3 ) n 44 38 n Sprouts n 0, 1, 2 (mod 6) 25 25: Sprouts (ii) A 2 ( A ) 6n 2 8n 3 Sprouts Brusseles Sprouts n free end 27

4n free end A B (i) free end (ii) free end (i) A B A B 26: n = 3 Brusseles Sprouts 39 Brusseles Sprouts 5n 2 n n Brusseles Sprouts p G G 1 1 2 n 0 V (G) = n + p, E(G) = 2p G free end free end ( (i) (ii) free end ) free end ( free end ) G free end 2 free end 2 free end free end 4n F (G) = 4n (n + p) 2p + 4n = 2 p = 5n 2 n Brusseles Sprouts B (ii) (A ) 28

4.4 T 40 T T S(T ) 1/2 T T x y T 1/2 41 (Pick, 1899) Q S(Q) S(Q) = n int + 1 2 n bound 1 n int Q n bound Q 27 Q n int = 1 n bound = 9 41 Q 1 + 9 2 1 = 9 2 27: ( ) ( ) 41. Q ( 27 ) T Q 40 S(Q) = 1 2 f f T Q ( ) T Q f T Q V (T Q ) = n int + n bound. 29

3 T Q n bound 2 E(T Q ) = 3f + n bound ( ) f + 1 = E(T Q ) V (T Q ) + 2 = 1 ) (3f + n bound ( ) n int + n bound + 2 2 = 3 2 f n int 1 2 n bound + 2. S(Q) = 1 2 f = n int 1 2 n bound 1. 42 m m = 4 m Q Q Q Q m m S(T ) S(T ) a S(T ) = 1 2 a2 sin(2π/m) a 2 2 ( ) sin(2π/m) m 4 S(T ) m 4 Q 43 5 K 5 ( ) 1 5 (x 1, y 1 ),..., (x 5, y 5 ) i, j {1, 2, 3, 4, 5} (x i, y i ) (x j, y j ) ( x i +x j, y i+y j ) 2 2 (, ), (, ), (, ) (, ) 4 5 (x 1, y 1 ),..., (x 5, y 5 ) i, j {1, 2, 3, 4, 5} x i + x j y i + y j (x i, y i ) (x j, y j ) m Z 3 m x 1,..., x m i, j {1, 2,..., m} ( i j) x i x j 44 T (, ), (, ), (, ) (, ) 4 T T 3 30

( ) T = ABC 3 A B AB ( 43 ) AB ( AB A B ) BC AC A, B, C T 41 T ( ) T = ABC 3 A B AB C BC AC C BC AC 41 T 44 T = ABC AB 3 AC 3 T S(T ) 8 4.5 ( ) 45 (Chvátal, 1975) n n 3 45 n 28 28 3 1 n 3 28: 45 46 G 2 G G G 2 G 2 G 31

G G 4 G 3 G n f G n 2 E(G) = 3f + n ( ) 3 f n n + (f + 1) = E(G) + 2 2 E(G) = n + 3f 2n + 2f = 2 ( E(G) + 1 ) G 2 47 3 G G 3 3 G 4 G v G v G v T v 3 v 2 v v 45. Fisk (1978) n Q T Q ( 3 ( ) ) V (T Q ) = n T Q 47 T Q 3 T Q n n 3 n 3 1 Q Q n+2 3 n Q (O Rourke, 1982) h n+2h 3 48 n n 4 48 n 4 3 32

49 (Hoffmann & Kriegel, 1996) Q n/3 n Q 50 T T 3 T 49. Zhang & He (2005) 45 Q 3 50 ( 3 ) ( ) 2, T ( 29 ) T 29: ( ) ( ) v C v C v Q R v X v ( 30 ) R v + X v x R v 2 C v x r 1, r 2 r 1 + r 2 = R v C v X v r 1 r 2 T v deg T (v) = X v + r 2 = X v + ( R v r 1 ) 0 (mod 2). 31 ( ) 33

v v = R v Q = X v 30: v ( ) C v R v X v ( ) 31: 4.6 3 ( 4 ) m 51 (Erős & Szekeres, 1935) m 3 m f(m) f(m) m m f(m) ( ) 2m 4 + 1 m 2 f(4) 5 f(5) 9 m 34

52 (Horton, 1983) N N 7 6 N 463 (Koshelev, 2007) 30 (Overmars, 2003) 35

5 5.1 53 (Sylvester Gallai ) n (n 3.) n 2 n S S 2 L l L S 3 n 1 l L l p S (l, p) p l (l 0, p 0 ) p 0 l 0 q 0 l 0 S 3 p 1, p 2 S l 0 q 0, p 1, p 2 ( q 0 = p 1 ) p 0 p 2 l 1 p 1 l 1 p 1 l 1 p 0 l 0 (l 0, p 0 ) ( 32 ) l 1 p 0 l 0 q 0 p 1 p 2 32: 53 1 54 G 5 G ( ) ( 6 dg (v) ) + ( 6 2dG (f) ) = 12. (5) v V (G) f F (G) d G (f) f 3 12 = ( ) v V (G) ( 6 dg (v) ) 5 (5) 36

Norman Steenrod n S S 2 53 n 3 n n 2 p C p p C p 2 1 C 2 p C, p C C p C p 2 p C, p C C 2 p C p C C k p 1,..., p k p C p C k C p 1,..., C pk ( ) 53 n 3 n n 2 n ( ) G G 2 G 4 54 G 4 v v 2 n 54 (5) n 2 3 55 n (n 3.) 2 n n n = 3 n 4 n S 53 S 2 l l S p S = S {p} S n 1 S 2 n 1 l S 2 n S n 1 l 0 S p p p S 2 37

n 1 l 0 S 2 n ( 33 ) p l 0 33: 55 S n 1 l 0 5.2 55 K n H 1, H 2,..., H m K n H i K n H 1, H 2,..., H m 56 K n H 1, H 2,..., H m m = 1 m n 28 n S S 2 G G 55 56 56 K n H 1, H 2,..., H m m 1 m < n +1 n x x H i x H i r x x H i 1 r x x x H k m r x H k. H k y K n xy H i m r x x H i r x m H k H k H k x V (H k ) x 1 r x x V (H k ) 1 r x x V (H k ) 38 1 m H k

x V (H k ) x n H k x V (H k ) 1 r x x V (H k ) 1 m H k = n H k m H k > n m n > m H k 1 n = ( ) > m n m = n 29 56 m n 56 m n H i n n = 7 7 V (K 7 ) = {0, 1, 2, 3, 4, 5, 6} H 1,..., H 7 V (H 1 ) = {0, 1, 6}, V (H 2 ) = {0, 2, 5}, V (H 3 ) = {0, 3, 4}, V (H 4 ) = {1, 2, 4}, V (H 5 ) = {1, 3, 5}, V (H 6 ) = {2, 3, 6}, V (H 7 ) = {4, 5, 6}. 56 55 ( ) K 7 34 1 4 5 0 2 3 6 34: 30 K n H i H 1, H 2,..., H n n t n = t 2 t + 1 n 7 13 (t = 4 ) n = 13 K 13 n 39

57 K n 2 H 1, H 2,..., H m m n 1 K n 2 H 1, H 2,..., H m m < n 1 H i 2 L i, R i K n v X v H 1, H 2,..., H m K n m ( ) X u X v = X s X t (6) i=1 s L i t R i u,v V (K n),u v X v = 0, v V (K n) s L i X s = 0 (i = 1,..., m). n m + 1 < n X v = α v (v V (K n )) (6) i s L i α s = 0 α u α v = 0 u,v V (K n),u v v V (K α n) v = 0, ( ) 2 0 = α v = αu 2 + v V (K n) v V (K n) u,v V (K n),u v α u α v = v V (K n) α v (v V (K n )) v V (K n) α2 u > 0 57 K n n = 1 n 2 1 v v 2 K 1,n 1 H n 1 K n v K n 1 2 K 1,n 2,... K 1,1 n 1 2 K n ( 35 n = 5 ) α 2 u K 5 H 4 H 3 H 2 H 1 35: H 1, H 2, H 3, H 4 K 5 H i K 1,i 31 35 (1 i n 1 H i K 1,i ) H i L i 1 57 i R i 1 40

5.3 ( ) ( ) 3 32 G n P 3 (3 ) E(G) n 2 58 (Turán, 1941) G n n n E(G). 2 2 59 Cauchy Schwarz a, b 2 a 2 b 2 a = (a 1,..., a n ) T b = (1,..., 1) T n = 2 59 n a 1,..., a n ( n ) 2 n a i n a 2 i. i=1 a 1 = a 2 = = a n 58. n E(G) n2 4 G A α (.) G α + 1 G u N G (u) d G (u) α B = V (G) A A G B E(G) u B d G(u) B = β α + β = n E(G) ( α + β ) 2 n 2 d G (u) αβ = 2 4. u B i=1 Mantel 58. E(G) n2 G n 4 G G uv d G (u) + d G (v) n ( ) d G (u) + d G (v) n E(G) uv E(G), u d G (u) d G (u) n E(G) ( ) d G (u) + d G (v) = ( 2. d G (u)) uv E(G) 41 u V (G)

59 u V (G) ( ) 2 1 ( d G (u) n u V (G) ) 2 4 E(G) 2 d G (u) = n 33 58 n 34 G n m G 4m 3n ) (m n2 4 Mantel 58 G uv uv d G (u) + d G (v) n 2 S = { (uv, T ) : uv E(G), T uv G }. 58 G n 59.1 G 3 u, v, w uv, uw E(G) vw E(G) u u v u v v v w w w 36: 3 u, v, w. 37: 59.1 1 3 u, v, w ( 36 ) 2 1: d G (u) < d G (v) d G (u) < d G (w) d G (u) < d G (v) G ( 37 ) u N(v ) = N(v) v 42

G vv E(G ) G T G T v vv E(G ) T v v v G G E(G ) = E(G) d G (u) + d G (v ) = E(G) d G (u) + d G (v) > E(G) G 2: d G (u) d G (v) d G (u) d G (w) G v, w N(u ) = N(u ) = N(u) u, u G 1 G E(G ) = E(G) ( d G (v) + d G (w) 1 ) + 2d G (u) > E(G) 59.1 59.1 58 2 u, v uv E(G) u v V (G) 2 59.1 G 2 G 2 G 2 K n1,n 2 ( n 1 + n 2 = n ) E(K n1,n 2 ) = n 1 n 2 n 2 n 2. 35 : G n K 4 E(G) n2 3. 60 (Turán, 1941) G n K k+1 E(G) ( 1 1 ) n 2 k 2 60 43

5.4 2 61 (Reiman, 1958) G n n ( ) E(G) 1 + 4n 3. 4 61. G n S 2 { (u, ) } S = {v, w} : v w uv, uw E(G). ( u, {v, w} ) S vw G u S = ( ) dg (u) = 1 ( ) 2 1 d G (u) d G (u) 2 2 2 u V (G) u V (G) u V (G) G {v, w} ( u, {v, w} ) S u S ( n 2) 1 2 u V (G) ( ) 2 1 d G (u) 2 u V (G) d G (u) ( ) 2 d G (u) n(n 1) + u V (G) 59 ( u V (G) u V (G) u V (G) ) 2 d G (u) n 2 (n 1) + n u V (G) ( ) n 2 d G (u). d G (u) d G (u) = 2 E(G) 4 ( E(G) ) 2 2n E(G) n 2 (n 1) 0 2 E(G) 36 G n K 2,3 E(G) n 3/2 61 S S t 2 G n K 2,t G 44

61 ( n p = t 1 30 n ) 62 p n = p 2 + p + 1 n G E(G) = n 1 ( ) 1 + 4n 3. 4 p Z p 3 X X = { v = (v 1, v 2, v 3 ) : v i Z p, i = 1, 2, 3 } Z p ( Z p ) X v [v] v 1 ( v 0 = (0, 0, 0) ) [v] = { u : u = kv, 0 k p 1 } [v] = p G p V (G p ) = { [v] : v X {0} }, E(G p ) = { [v][w] : [v] [w], v, w = v 1 w 1 + v 2 w 2 + v 3 w 3 = 0 }. v, w = 0 [v] [w] well-defined ( kv [v] v, w = 0 kv, w = 0 ) 37 p = 3 G 3 1 [v] 0 p 1 X 0 p 3 1 X v w [v] [w] = {0} [v] = [w] V (G p ) = p3 1 p 1 = p2 + p + 1 = n G p 2 [v] [w] G p [u] [u][v], [u][w] E(G p ) G p u = (u 1, u 2, u 3 ) x = (x 1, x 2, x 3 ) : v 1 x 1 + v 2 x 2 + v 3 x 3 = 0, w 1 x 1 + w 2 x 2 + w 3 x 3 = 0. v = (v 1, v 2, v 3 ) w = (w 1, w 2, w 3 ) [v] [w] G p v w 1 45

1 [u] 1 [v] [w] G p [u] G p G p G p [v] v 1 x 1 + v 2 x 2 + v 3 x 3 = 0 Xv 2 Xv 0 p 2 1 X 1 0 p 1 Xv p 2 1 p 1 = p + 1 1 [v] G p 1 p + 1 2 E(G p ) (p + 1)n n = p 2 + p + 1 p = 1+ 4n 3 2 E(G p ) (p + 1)n 2 = n ( ) 1 + 4n 3 4 Xv p + 1 1 [v] G p p + 1 [v] G p [v] d Gp ([v]) = p { p + 1 (v1 ) 2 + (v 2 ) 2 + (v 3 ) 2 0 (v 1 ) 2 + (v 2 ) 2 + (v 3 ) 2 = 0 (7) p (x 1 ) 2 + (x 2 ) 2 + (x 3 ) 2 = 0 x = (x 1, x 2, x 3 ) 62.1 (x 1 ) 2 + (x 2 ) 2 + (x 3 ) 2 = 0 p + 1 [v] 62.1 62 62.1 (7) G p p [v] p + 1 G p p 2 + p + 1 p + 1 p 2 2 E(G p ) = p(p + 1) + (p + 1)p 2 = p(p + 1) 2 n = p 2 + p + 1 E(G p ) = p(p + 1)2 2 = p2 + p 4 ( ) n 1( ) 1 + (2p + 1) = 1 + 4n 3 4 62.1 62.1 X 1 [v (1) ], [v (2) ],..., [v (n) ] n n A 46

A i j v (i), v (j) = 0 1 0 v (i) (x 1 ) 2 + (x 2 ) 2 + (x 3 ) 2 = 0 v (i), v (i) = 0 A 62.1 A 1 A trace ( ) trace A = (A ). A A 2 A i v (i) 1 x 1 + v (i) 2 x 2 + v (i) 3 x 3 = 0 x = (x 1, x 2, x 3 ) 1 1 ( v (i) = (v (i) 1, v (i) 2, v (i) 3 ) ) 1 p + 1 A 2 i i ( ) p + 1 p + 1 p + 1 A 1 1 A1 = (p + 1)1 p + 1 A 1 A i j v (i) 1 x 1 + v (i) 2 x 2 + v (i) 3 x 3 = 0 v (j) 1 x 1 + v (j) 2 x 2 + v (j) 3 x 3 = 0 x = (x 1, x 2, x 3 ) 1 1 A 2 i j 1 A 2 p + 1 1 1 A 2 1 p + 1 1 =...... 1 1 p + 1 = pi + J. J 1 n n I J n ( 1) 0 ( n 1) A 2 n + p ( 1) p ( n 1) A A ± n + p ( 1) ± p ( n 1) p + 1 A ( n + p = p 2 + 2p + 1 = p + 1 ) A p s p t trace A = (A ) = (p + 1) + s p t p 47

A p s = t A p + 1 62.1 p = 3 A A 2 48

6 6.1 2 3 G G cr(g) G cr(g) = 0 2 K 3,3 cr(k 3,3 ) = 1 G 2 63 (Truán, 1940s) n, m cr(k n,m ) = n n 1 m m 1. 2 2 2 2 K n m cr(k n,m ) ( n 2)( m 2 ) ( ) 63 ( ) 64 63 ( ) K 5,6 38 38: K 5,6 49

39 n, m 38 63 63 n = 3 58 65 63 K 3,m 64 K 3,m 3 2 m m 1 m m 1 = 2 2 2 2 2 2 y 1 x 1 y 4 y 4 y 3 y 1 y 3 y 2 x 2 y 2 x3 39: K 3,4 H (X = {x 1, x 2, x 3 } ) K 3,m X Y 3 X m Y y Y y K 3,m E(y) E(y) = 3 K 3,m φ Y H Y 2 y 1, y 2 E(y 1 ) E(y 2 ) φ H y 1 y 2 E(H) = {y 1 y 2 : E(y 1 ) E(y 2 ) φ } ( 39 ) φ E(H) m m 1 E(H) 2 2 H H H H 2 ( E(H) = {y 1 y 2 : y 1 y 2 E(H)}.) K 3,3 65.1 H H y 1 y 2 y 3 H H E(y 1 ), E(y 2 ), E(y 3 ) X y 1, y 2, y 3 K 3,3 K 3,3 50

58 H m m E(H) 2 2 E(H) ( ) m m(m 1) E(H) = E(H) 2 2 m m 2 2 = m 2 m 1 2. 63 n ( m) 66 n, m cr(k n,m ) n n 2 cr(k n 1,m). 2 K n,m S 2 S = { (p, H) : p K n,m H K n 1,m p }. K n,m n n 1 K n 1,m H H cr(k n 1,m ) H n S n cr(k n 1,m ) K n,m p p K n,m n 2 2 H p H n 2 p cr(k n,m ) S = (n 2) cr(k n,m ) 66 40 66 63 n K 4,m K n cr(k n ) 2 K n 67 (Hill, 1960) n cr(k n ) = 1 4 n n 1 n 2 n 3, 2 2 2 2 51

67 K n n 12 67 n 41 n cr(k n ) n n 4 cr(k n 1). (rectilinear crossing number) K n n 27 42 cr(k 6 ) = 3 6.2 G cr(g) 68 G n = V (G), m = E(G) cr(g) m 3n 68. G n = V (G), m = E(G) G t t m 3n G G G G V (G ) = n + t 2 4 E(G ) = m + 2t E(G ) 3 V (G ) m + 2t 3 ( n + t ) 6 t m 3n + 6 H E(H) 3 V (H) 3 E(H) 3 V (H) E(H) 3 V (H) 6 E(H) 3 V (H) 6 52

69 ( ) G n = V (G), m = E(G) m 4n cr(g) m3 64n. 2 69. G G p (0 p 1) G p ( xy x y G p ) n p, m p X p G p 68 H cr(h) E(H) + 3 V (H) 0 Ex(X p m p + 3n p ) 0 Ex(n p ), Ex(m p ), Ex(X p ) G p Ex(n p ) = pn G Ex(m p ) = p 2 m G G p 2 G p 4 G p Ex(X p ) = p 4 cr(g) 0 Ex(X p ) Ex(m p ) + 3Ex(n p ) = p 4 cr(g) p 2 m + 3pn cr(g) m p 2 3n p 3. p = 4n/m m 4n p 1 cr(g) m 3n ( ) 2 ( ) 3 = 1 ( 4nm 3 3nm 3 ) 4n/m 4n/m 64 n 3 = m3 64n 2. 6.3 70 n S A = { {p, p } : p, p S, p p 1 } A < 8n 4/3. S p p 1 C p 1/19 53

70.1 p S C p, C p p S C p S 70.1 p S A p C p C p p B = { (p, C q ) : p, q S, p C q } B = 2 A G V (G) = S E(G) = {pp : q S p, p C q C q p p S }. G E(G) C q C q C q 2 G cr(g) ( ) n cr(g) 2 < n 2. 2 cr(g) 69 ( ) 70.1 G 2 p, p p p C q 2 q S B 2 (p, C q ) (p, C q ) E(G) 1 4 B = 1 2 A E(G) 4n = 4 V (G) A 2 E(G) 8n 8n 4/3 E(G) > 4n G cr(g) 1 E(G) 3 1 A 3 64 n 2 512 n 2 A 3 512n 2 cr(g) < 512n 4 70 70 A O(n 4/3 ) Erdős $500 71 (Erdős, 1946) 70 A a, c n 1+c/ log log n A a n 54

6.4 2 72 (Szemerédi and Trotter, 1983) S L A = { (p, l) : p S, l L, p l } A max { 4 S + L 1, 4 S 2/3 L 2/3 + L }. Székely L G V (G) = S, E(G) = {(p, p ) : p p l L } 43 G 72 55