11 okamotoy@uec.ac.jp 2019 1 25 2019 1 25 10:59 ( ) (11) 2019 1 25 1 / 38
1 (10/5) 2 (1) (10/12) 3 (2) (10/19) 4 (3) (10/26) (11/2) 5 (1) (11/9) 6 (11/16) 7 (11/23) (11/30) (12/7) ( ) (11) 2019 1 25 2 / 38
( ) 8 (2) (12/14) 9 (1) (12/21) 10 (2) (1/11) (1/18) 11 (1/25) 12 (2/1) 13 (2/8) (2/15 ) ( ) ( ) (11) 2019 1 25 3 / 38
Lovász Lovász ( ) (11) 2019 1 25 4 / 38
1 2 3 Lovász 4 Lovász 5 Lovász 6 ( ) (11) 2019 1 25 5 / 38
n 1 A R n n A (positive semidefinite matrix) x R n ( ) 1 0 0 0 x Ax 0 ( ) ( ) ( ) 1 0 x x y = x 2 0 0 y A A O A A ( ) (11) 2019 1 25 6 / 38
n 1 A R n n 1 A 2 A ( ) 3 J {1, 2,..., n} det(a JJ ) 0 A JJ J J A 4 L R n r A = LL r = rank A (A (Cholesky decomposition)) ( ) 1 0 1, 0 0 0 0 ( ) ( ) 1 0 1 (1 ) = 0 0 0 0 ( ) (11) 2019 1 25 7 / 38
n 1 S n R n n n S+ n R n n n ( ) ( ) ( ) 1 0 3 1, S 2 1 2 +, S+ 0 0 1 2 2 1 2 S n + S n + ( ) (11) 2019 1 25 8 / 38
1 2 3 Lovász 4 Lovász 5 Lovász 6 ( ) (11) 2019 1 25 9 / 38
(semidefinite programming) n 1, m 0 C, A 1,..., A m R n n b 1,..., b m R ( X ) maximize C X subject to A i X = b i (i {1,..., m}) X O n n C X = C ij X ij = tr(c X ) i=1 j=1 ( ) (11) 2019 1 25 10 / 38
max. C X max. c x s. t. A i X = b i (i {1,..., m}) X O s. t. a i x = b i (i {1,..., m}) x 0 ( ) (11) 2019 1 25 11 / 38
maximize C X subject to A i X = b i (i {1,..., m}) X O { = X S n A i X = b i X O (i {1,..., m}) } {X X O} (S n + ) A i X = b i A i X b i A i X b i 2 ( ) (11) 2019 1 25 12 / 38
( ) maximize C X subject to A i X = b i (i {1,..., m}) X O { = X S n A i X = b i X O (i {1,..., m}) } ( ) (11) 2019 1 25 13 / 38
1 2 3 Lovász 4 Lovász 5 Lovász 6 ( ) (11) 2019 1 25 14 / 38
László Lovász (1948 ) http://web.cs.elte.hu/ lovasz/ ( ) (11) 2019 1 25 15 / 38
Lovász G = (V, E) n = V Lovász G Lovász (Lovász number) (LOV) maximize u V v V X uv subject to X uv = 0 ({u, v} E) X vv = 1 v V X O ( X S+) n G Lovász ϑ(g) ( ) (11) 2019 1 25 16 / 38
Lovász G = (V, E) n = V Lovász G Lovász ϑ(g) (LOV) maximize u V v V X uv subject to X uv = 0 ({u, v} E) X vv = 1 v V X O ( X S+) n ( ) (11) 2019 1 25 17 / 38
Lovász G = (V, E) Lovász ω(g) ϑ(g) χ(g) Lovász 1 ω(g) ϑ(g) 2 ϑ(g) χ(g) ( ) (11) 2019 1 25 18 / 38
Lovász (1) C G y R n { 1 (v C) y v = 0 (v C) X = 1 C yy ( ) (11) 2019 1 25 19 / 38
Lovász (2) X = 1 C yy X (LOV) X (c.f. ) {u, v} E u, v C v V X vv = v V X uv = 1 C y uy v = 0 1 C y v 2 = 1 C C = 1 X uv ϑ(g) = (LOV) u V v V = 1 C y uy v = 1 C C 2 = C = ω(g) u V v V ( ) (11) 2019 1 25 20 / 38
Lovász G = (V, E) Lovász ω(g) ϑ(g) χ(g) Lovász 1 ω(g) ϑ(g) ( ) 2 ϑ(g) χ(g) ( ) (11) 2019 1 25 21 / 38
Lovász (1) X (LOV) χ(g) = k V k V 1,..., V k j {1,..., k} y j R n { yv j 1 (v V j ) = 0 (v V j ) ( ) (11) 2019 1 25 22 / 38
Lovász (2) X (ky j 1) X (ky j 1) 0 0 k (ky j 1) X (ky j 1) j=1 k = k 2 y j X y j 2k j=1 k = k 2 k y j X 1 + j=1 k 1 X 1 j=1 X vv 2k1 X 1 + k1 X 1 j=1 v V j = k 2 X vv k X uv v V u V v V = k 2 kϑ(g) ϑ(g) k = χ(g) ( ) (11) 2019 1 25 23 / 38
Lovász G = (V, E) Lovász ω(g) ϑ(g) χ(g) Lovász 1 ω(g) ϑ(g) ( ) 2 ϑ(g) χ(g) ( ) ( ) (11) 2019 1 25 24 / 38
1 2 3 Lovász 4 Lovász 5 Lovász 6 ( ) (11) 2019 1 25 25 / 38
Lovász G = (V, E) n = V Lovász G Lovász (Lovász number) (LOV) maximize G Lovász ϑ(g) u V v V X uv subject to X uv = 0 ({u, v} E) X vv = 1 v V X O ( X S n +) ϑ(g) ( ) (11) 2019 1 25 26 / 38
ϑ(g) χ(g) X ( ) 2 Xuv 2 X uv χ(g) 2 u V v V u V v V χ(g) ( ) ( ) (11) 2019 1 25 27 / 38
(1) (LOV) = X S n X uv = 0 ({u, v} E) X vv = 1 v V X O n 2 1 n(n + 1) E 1 2 X ( ) 1 (u = v) X uv = n 0 (u v) ( ) (11) 2019 1 25 28 / 38
(2) X uv = 0 ({u, v} E) (LOV) = X S n X vv = 1 v V X O X A R n n i a ii a ij j i ( ) (11) 2019 1 25 29 / 38
(1) A R n n A λ 1 x x x i k (x k 0 ) Ax = λx k n a kj x j = λx k j=1 a kj x j = (λ a kk )x k j k ( ) (11) 2019 1 25 30 / 38
(2) ( ) x k 0 a kj x j j k λ a kk = a kj x j x k x k j k A λ a kk a kk a kj j k λ [0, 2a kk ] λ 0 ( ) (11) 2019 1 25 31 / 38
Lovász G = (V, E) n = V Lovász G Lovász (Lovász number) (LOV) maximize u V v V X uv subject to X uv = 0 ({u, v} E) X vv = 1 v V X O ( X S n +) Lovász ( ) (11) 2019 1 25 32 / 38
1 2 3 Lovász 4 Lovász 5 Lovász 6 ( ) (11) 2019 1 25 33 / 38
Lovász ω(g) ϑ(g) χ(g) ϑ(g) G ω(g) = χ(g) ω(g) = ϑ(g) = χ(g) ϑ(g) ω(g), χ(g) ( ) (11) 2019 1 25 34 / 38
1 2 3 Lovász 4 Lovász 5 Lovász 6 ( ) (11) 2019 1 25 35 / 38
Lovász Lovász ( ) (11) 2019 1 25 36 / 38
( ) OK OK ( ) (11) 2019 1 25 37 / 38
1 2 3 Lovász 4 Lovász 5 Lovász 6 ( ) (11) 2019 1 25 38 / 38