오일러의볼록다면체정리의일반화 김상욱 전남대학교 제 2 회무등수학강연회 2011 년 11 월 4 일 김상욱 ( 전남대학교 ) 오일러의볼록다면체정리의일반화 Nov. 4, 2011 1 / 36

Outline 1 3 차원볼록다면체 2 볼록다면체의면벡터 3 볼록다면체의플래그벡터 4 볼록다면체의 cd- 지수 김상욱 ( 전남대학교 ) 오일러의볼록다면체정리의일반화 Nov. 4, 2011 2 / 36

3 차원볼록다면체 정의 3 차원볼록다면체란다각형들을면으로갖는내부가볼록집합인입체도형이다. 3 차원볼록다면체 김상욱 ( 전남대학교 ) 오일러의볼록다면체정리의일반화 Nov. 4, 2011 4 / 36

3 차원정다면체 정다면체 ( 플라톤의다면체 ) 는고대부터알려져왔다. 정다면체들 피타고라스 (Pythagoras, 570-495 BC) - 정 4 면체, 정 6 면체, 정 12 면체 테아에테우스 (Theaetetus, 417-369 BC) - 정 8 면체, 정 20 면체 유클리드 (Euclid, 365-275 BC) - 정다면체에대한완벽한수학적기술 ( 원론 (Elements)) 김상욱 ( 전남대학교 ) 오일러의볼록다면체정리의일반화 Nov. 4, 2011 5 / 36

데카르트의유작 (Nachlass) 정리 ( 데카르트 (Descartes, 1596-1650)) 3 차원볼록다면체에서 v : 꼭지점의개수 f : 면의개수 ρ : 평면각 ( 면위에있는꼭지점들에서의각 ) 의개수 들은다음식을만족한다. many closed halfspaces, where it is assumed that this intersection is bounded. It is a basic theorem that this second construction principle leads to the same class of objects as the one described a moment ago. In addition there is a combinatorial duality at work under which, e.g., the octahedron corresponds to the cube. Again: When the defining hyperplanes are in general position then no more than d of them will go through the same point. It follows that in this case each vertex lies in exactly d facets. Such a polytope is called simple. Combinatorially, simplicial and simple polytopes are dual to each other. 2 When Descartes died in Stockholm, 11 February 1650, his mathematical Nachlass remained in Sweden for a few years, and then was sent to Paris. It arrived there in bad condition but nevertheless was published in part by 1667. In 1676 Leibniz had a chance to look at some of the unpublished material, and among these papers he found a handwritten note Progymnasmata De Solidorum Elementis that took his interest, and he copied part of it to take home. Descartes original note went lost, and Leibniz copy [2] remained unpublished at the time. It took 200 years until it was found in an uncatalogued part of Leibniz Nachlass at the Royal Library of Hanover. Fig. 2, taken from [4], shows an enlargement from the relevant page. Mathematically it says the following: Consider a polyhedron, i.e., a polytope in R 3. Let α be the number of solid angles (i.e., vertices), φ be the number of facets, and ρ be the number of plane angles (i.e., angles at the vertices of the facets). By arguing about the sum Σ of these plane angles Descartes proves that ρ = 2v + 2f 4. ρ = 2φ + 2α 4. (3) 데카르트의노트를복사한 Fig. 2 라이프니쯔의노트 2 김상욱 ( 전남대학교 ) 오일러의볼록다면체정리의일반화 Nov. 4, 2011 6 / 36

데카르트의유작 (Nachlass) 예제 v = 5 f = 5 ρ = 16 ρ = 2v + 2f 4. 모서리의개수를이용한표현 각각의평면각은두개의모서리를포함하고있고각각의모서리는네개의평면각에포함되므로 ρ 는모서리의개수 e 의두배이다. 그러므로 v e + f = 2. 김상욱 ( 전남대학교 ) 오일러의볼록다면체정리의일반화 Nov. 4, 2011 7 / 36

오일러의정리 정리 ( 오일러, 1758) 3 차원볼록다면체의꼭지점의개수를 v, 모서리의개수를 e, 면의개수를 f 라하면 v e + f = 2 가성립한다. 1750 년 Goldbach 에게보낸편지에서처음소개됨. 1752/1753 년 Petersberg Academy s Proceeding 에소개됨. 오일러에의해다면체의모서리라는표현이처음사용됨. 김상욱 ( 전남대학교 ) 오일러의볼록다면체정리의일반화 Nov. 4, 2011 8 / 36

오일러의정리 오일러정리의증명 3 차원볼록다면체의꼭지점과모서리들은평면그래프를이룬다. 평면그래프가 v 개의점, e 개의선분, f 개의영역을가지면, v e + f = 2 가만족됨을선분의개수에관한수학적귀납법으로증명할수있다. 볼록다면체 Schlegel 다이어그램 김상욱 ( 전남대학교 ) 오일러의볼록다면체정리의일반화 Nov. 4, 2011 9 / 36

Steinitz 정리 질문 v e + f = 2 를만족하는 v, e, f 에대하여 v 개의꼭지점, e 개의모서리, f 개의면을갖는 3 차원볼록다면체가항상존재하는가? 아니다! 정리 (Steinitz, 1906) v, e, f 가각각 3 차원볼록다면체의꼭지점의수, 모서리의수, 면의수가되기위한필요충분조건은다음과같다. v e + f = 2 f 2v 4 v 2f 4 김상욱 ( 전남대학교 ) 오일러의볼록다면체정리의일반화 Nov. 4, 2011 10 / 36

Steinitz 정리 f 4 2 f 2 = 2f 0 4 인경우모든면이삼각형이다. 정 4 면체, 정 8 면체, 정 20 면체단체다면체 (simplicial polytope) f 4 0 f 0 = 2f 2 4 인경우모든점이세개의모서리에접한다. 정 4 면체, 정 6 면체, 정 12 면체단순다면체 (simple polytope) 김상욱 ( 전남대학교 ) 오일러의볼록다면체정리의일반화 Nov. 4, 2011 11 / 36

Steinitz 정리의증명 ( 필요조건 ) 다면체의각면은적어도 3 개의모서리에인접하고각각의모서리는두개의면에인접하므로 3f 2e f 2v 4 다면체의각꼭지점은적어도 3 개의모서리에인접하고각각의모서리는두개의꼭지점에인접하므로 3v 2e v 2f 4 김상욱 ( 전남대학교 ) 오일러의볼록다면체정리의일반화 Nov. 4, 2011 12 / 36

Steinitz 정리의증명 ( 충분조건 ) 주어진조건을만족하는 v, e, f 에대하여 v 개의꼭지점, e 개의모서리, f 개의면을갖는 3 차원볼록다면체를찾아내면된다. n 각뿔의경우 : v = n + 1, e = 2n, f = n + 1 김상욱 ( 전남대학교 ) 오일러의볼록다면체정리의일반화 Nov. 4, 2011 13 / 36

Steinitz 정리의증명 ( 충분조건 ) 다면체의삼각형면위에사면체를붙일경우 : v v + 1, e e + 3, f f + 2 김상욱 ( 전남대학교 ) 오일러의볼록다면체정리의일반화 Nov. 4, 2011 14 / 36

Steinitz 정리의증명 ( 충분조건 ) 3 개의모서리에인접한꼭지점을잘라내는경우 : v v + 2, e e + 3, f f + 1 김상욱 ( 전남대학교 ) 오일러의볼록다면체정리의일반화 Nov. 4, 2011 15 / 36

Steinitz 정리의증명 ( 충분조건 ) v, e, f 가 v e + f = 2, f 2v 4, v 2f 4 를만족한다고하자. Case 1. v = f + k 인경우 : v 2f 4 에의해 f k 1 3 (f k 1) 각뿔을만든다. 세개의모서리에인접한꼭지점을잘라내기를 k 번반복하면꼭지점이 v 개, 모서리가 e 개, 면이 f 개인볼록다면체를얻을수있다. Case 2. f = v + k 인경우 : f 2v 4 에의해 v k 1 3 (v k 1) 각뿔을만든다. 삼각형면위에사면체를붙이기를 k 번반복하면꼭지점이 v 개, 모서리가 e 개, 면이 f 개인볼록다면체를얻을수있다. 김상욱 ( 전남대학교 ) 오일러의볼록다면체정리의일반화 Nov. 4, 2011 16 / 36

볼록다면체의면 정의 예제 볼록다면체는유한개의점의최소볼록집합 (convex hull) 이다. P = conv{v 1, v 2,..., v n } R d 볼록다면체 P 의면 (face) 은 P 의받침초평면 (supporting hyperplane) 과 P 의교집합이다. 0 차원면 ( 꼭지점 ) 1 차원면 ( 모서리 ) -1 차원면 ( 공집합 ) 김상욱 ( 전남대학교 ) 오일러의볼록다면체정리의일반화 Nov. 4, 2011 18 / 36

볼록다면체의 f - 벡터 정의 볼록다면체 P의 f -벡터는 ( ) f 1 (P), f 0 (P), f 1 (P),..., f d 1 (P) 이다. 여기서 f i (P) 는 P 의 i- 차원면들의개수를나타낸다. 예제 P 의 f - 벡터는 (1, 5, 8, 5). P 김상욱 ( 전남대학교 ) 오일러의볼록다면체정리의일반화 Nov. 4, 2011 19 / 36

볼록다면체의 f - 벡터 질문 d- 차원볼록다면체의 f - 벡터가될수있는필요충분조건은무엇인가? 정리 (d = 2) (1, f 0, f 1 ) 이볼록다각형의 f - 벡터가될필요충분조건은 f 0 = f 1 이다. (d = 3) Steinitz 정리 Euler-Poincaré 정리 (Schläfli, 1901) d- 차원볼록다면체에대하여 f 0 f 1 + + ( 1) d 1 f d 1 = 1 ( 1) d. Poincaré 에의하여호몰로지이론을이용하여처음증명됨. Bruggesser 와 Mani 에의해 shelling 을이용하여증명됨 (1969) 김상욱 ( 전남대학교 ) 오일러의볼록다면체정리의일반화 Nov. 4, 2011 20 / 36

단체다면체 정의 단체다면체 (simplicial polytope) 은최고차원면이모두단체 (simplex) 인볼록다면체이다. 정리 (g- 추측 (McMullen, 1971); g- 정리 (Billera and Lee, 1980)) 단체다면체의 f - 벡터가될필요충분조건은다음식들로표현된다 일차방정식들 (Dehn-Sommerville 방정식들 ) 일차부등식들 비선형부등식들 단체다면체가아니고 dim 4 인경우 아직연구중. f - 벡터보다더많은정보가필요함. 김상욱 ( 전남대학교 ) 오일러의볼록다면체정리의일반화 Nov. 4, 2011 21 / 36

단체다면체의 h- 벡터 정의 단체다면체 P 와 k = 0, 1,..., d 에대하여 h k = k i=0 ( ) d i ( 1) k i f i 1 k i (h 0, h 1,..., h d ) 를다면체 P 의 h- 벡터라고한다. 정리 단체다면체의 f -벡터와 h-벡터는다음방정식에의해서로유일하게표현된다. d d f i 1 (t 1) d i = h i t d i i=0 i=0 김상욱 ( 전남대학교 ) 오일러의볼록다면체정리의일반화 Nov. 4, 2011 22 / 36

단체다면체의 h- 벡터 예제 P 의 f - 벡터 : (1, 6, 12, 8). 1(t 1) 3 + 6(t 1) 2 + 12(t 1) 1 + 8 = t 3 + 3t 2 + 3t + 1 P P 의 h- 벡터 : (1, 3, 3, 1). 정리 (Dehn-Sommerville 방정식들 ) 단체다면체 P 의 h- 벡터는다음방정식을만족한다. h k (P) = h d k (P) 김상욱 ( 전남대학교 ) 오일러의볼록다면체정리의일반화 Nov. 4, 2011 23 / 36

볼록다면체의플래그 f - 벡터 정의 S = {s 1 < s 2 < < s k } 를 {0, 1,..., d 1} 의부분집합이라하자. 볼록다면체 P 의 S- 플래그는 dim F i = s i 를만족하는면들의사슬 (chain) F 1 F 2 F k P 이다. f S (P) 는 P 의 S- 플래그들의개수이다. 벡터 (f S (P)) S {0,1,...,d 1} 를 P 의플래그 f - 벡터라고한다. 예제 P S f S (P) 1 0 5 1 8 2 5 01 16 02 16 12 16 012 32 김상욱 ( 전남대학교 ) 오일러의볼록다면체정리의일반화 Nov. 4, 2011 25 / 36

일반적인 Dehn-Sommerville 방정식 정리 (Bayer-Billera, 1983) d- 차원볼록다면체의플래그 f - 벡터들의성분으로만들어진선형생성부분공간 (linear span) 의차원은 d- 번째피보나치수이다. 플래그 f - 벡터의성분들이만족하는일차방정식을일반적인 Dehn-Sommerville 방정식이라고한다. 일차독립인플래그 f -벡터의성분들 3-차원 : f, f 0, f 1 4-차원 : f, f 0, f 1, f 2, f 02 5-차원 : f, f 0, f 1, f 2, f 3, f 02, f 03, f 13 김상욱 ( 전남대학교 ) 오일러의볼록다면체정리의일반화 Nov. 4, 2011 26 / 36

플래그벡터가만족하는부등식 정리 (Kalai, 1987) ( ) d + 1 f 02 3f 2 + f 1 df 0 + 0 2 정리 (4- 차원볼록다면체에서만족되는일차부등식들, Bayer, 1997) f 0 0 f 3 0 f 02 3f 2 0 f 02 3f 1 0 f 02 3f 2 + f 1 4f 0 + 10 0 6f 1 6f 0 f 02 0 김상욱 ( 전남대학교 ) 오일러의볼록다면체정리의일반화 Nov. 4, 2011 27 / 36

볼록다면체의플래그 h- 벡터 정의 P 를 d- 차원볼록다면체라고하자. P 의플래그 h- 벡터 (h S (P) : S {0, 1,..., n 1}) 는다음과같이정의된다. h S (P) := T S( 1) S T f T (P). 정리 ( 일반적인 Dehn-Sommerville 방정식 ) d-차원의볼록다면체 P에대하여다음방정식이만족된다. h S (P) = h T (P) 여기서 T = {0, 1,..., d 1} S이다. 김상욱 ( 전남대학교 ) 오일러의볼록다면체정리의일반화 Nov. 4, 2011 28 / 36

볼록다면체의플래그 h- 벡터 예제 P S f S (P) h S (P) 1 1 0 5 4 1 8 7 2 5 4 01 16 4 02 16 7 12 16 4 012 32 1 김상욱 ( 전남대학교 ) 오일러의볼록다면체정리의일반화 Nov. 4, 2011 29 / 36

볼록다면체의 cd- 지수 정의볼록다면체 P의 ab-지수는다음비가환다항식이다. ab(p) := h S (P) u 0 u 1 u d 1. S {0,1,...,d 1} 여기서 { a if i / S u i := b if i S 정리 / 정의 볼록다면체 P 의 ab- 지수는 c = a + b and d = ab + ba 의비가환다항식으로유일하게표현된다. 이다항식을 P 의 cd- 지수라하고 Ψ(P) 로나타낸다. 김상욱 ( 전남대학교 ) 오일러의볼록다면체정리의일반화 Nov. 4, 2011 31 / 36

볼록다면체의 cd- 지수 예제 S f S (P) h S (P) ab-단항식 1 1 aaa 0 5 4 baa 1 8 7 aba 2 5 4 aab 01 16 4 bba 02 16 7 bab 12 16 4 abb 012 32 1 bbb P ab(p) = a 3 + 4ba 2 + 7aba + 4a 2 b + 4b 2 a + 7bab + 4ab 2 + b 3 김상욱 ( 전남대학교 ) 오일러의볼록다면체정리의일반화 Nov. 4, 2011 32 / 36

볼록다면체의 cd- 지수 예제 P ab(p) =a 3 + 4a 2 b + 7aba + 4ab 2 + 4ba 2 + 7bab + 4b 2 a + b 3 = (a + b) 3 + 3(a + b)(ab + ba) + 3(ab + ba)(a + b) (c = a + b, d = ab + ba) Ψ(P) = c 3 + 3cd + 3dc 김상욱 ( 전남대학교 ) 오일러의볼록다면체정리의일반화 Nov. 4, 2011 33 / 36

볼록다면체의 cd- 지수 정리 (Bayer and Klapper, 1991) 볼록다면체의 cd- 지수는볼록다면체의플래그벡터와일차동등 (linearly equivalent) 하다. d- 차원볼록다면체의 cd- 지수의항의개수는 d 번째피보나치수이다. cd- 지수가존재할필요충분조건은일반적인 Dehn-Sommerville 방정식이만족되는것이다. 정리 (Stanley, 1994) 볼록다면체의 cd- 지수의계수들은언제나 0 보다크거나같다. 정리 (Billera & Ehrenborg, 2000) 볼록다면체의 cd- 지수의계수들은단체 (simplex) 의 cd- 지수보다항별로크거나같다. 김상욱 ( 전남대학교 ) 오일러의볼록다면체정리의일반화 Nov. 4, 2011 34 / 36

볼록다면체의 cd- 지수 정리 (Ehrenborg and Readdy, 1998) P를볼록다면체라하자. [ Ψ(Pyr(P)) = 1 Ψ(P) c + c Ψ(P) + 2 σ Ψ(σ) d Ψ(P/σ) ], Ψ(Prism(P)) = Ψ(P) c + σ Ψ(Bipyr(P)) = c Ψ(P) + σ Ψ(σ) d Ψ(P/σ), Ψ(σ) d Ψ(P/σ), 정리 (Ehrenborg and Fox, 2003) 다면체 P 와 Q 에대하여, Ψ(P Q) 은 Ψ(P) 와 Ψ(Q) 로부터계산할수있다. 김상욱 ( 전남대학교 ) 오일러의볼록다면체정리의일반화 Nov. 4, 2011 35 / 36

볼록다면체의 cd- 지수 정리 (K.) P 가볼록다면체이고 H 가 P 의내부와만나는초평면이라하면 Ψ(P) = Ψ(P + ) + Ψ(P ) Ψ( P) c σ Ψ(ˆσ) d Ψ( P/ˆσ). 여기서 P + = P H +, P = P H, P = P H, ˆσ = σ H 이고마지막합은 H 로인해만들어지는두개의반공간과만나는면 σ 에대한합이다. 예제 1 H + 2 P + P 4 H 5 := 23 H 3 Ψ(1234) =Ψ(125) + Ψ(1345) Ψ(15) c Ψ(5) d Ψ(15/5) 김상욱 ( 전남대학교 ) 오일러의볼록다면체정리의일반화 Nov. 4, 2011 36 / 36