저희가 보통 귀납법적인 증명을 할 때는
case i) n = 1 일 때 증명,
case ii) n = k 일 때 성립한다고 가정하고 n = k + 1 일 때도 성립한다는 걸 보이기
인데, 저건 K^1 -> K^2 일 때를 n = 1 이라고 본 거잖아요. 그러면 저대로 계속 expanding 하면 complete graph 들만 나오는 격인데,
증명에서 n = k 인 케이스를 non-trivial perfect graph 라고 가정하고 증명을 이어나가잖아요.
그럼 non-trivial perfect graph 에 대한 n = 1 일 때의 증명은 어디간거죠?
아니 애초에 non-trivial perfect graph 에 대한 어떤 order 를 줘서 귀납법을 논할 수가 있나요?
저기서 보이는건 perfect graph G의 임의의 vertex 하나 잡아서 expanding한 그래프를 G"라 했을때 그것도 perfect인걸 보이는거잖아요. 그래서 G의 vertex set의 크기에 대한 induction을 쓴거고요. G'가 perfect인걸 보이려면 임의의 induced subgraph H에 대해서 x(H)=w(H)란걸 보여야 하는데, H가 G'의 proper induced subgraph이면 G의 proper induced subgraph이거나 (이건 G가 perfect이니까 당연히 perfect) G의 proper induced subgraph에서 vertex 하나 잡아 expanding 한거니까, 본문과 같이 귀납가정에 의해서 이 경우는 당연히 perfect이 되고요.
음 그러니까 제 말은 버텍스 셋의 크기에 따라 induction 을 하면 안되지 않나라는 생각이 들어서에요. induction 자체가 n = 1, 2, 3, ... 일 때 계속 성립해 나가니까 쓰는 건데, n = 1 을 증명할때 trivial(complete) 이라는 조건 하나가 더 들어갔잖아요. 그러니까 n = 1 & G is trivial 이라고 기준을 정했으면 n = k 일 때도 G is trivial 이어야지 않나라는 생각이 들어서요
요약하자면 어떤 perfect graph G와 그것의 vertex x에 대해서, P(G,x) : G의 vertex x에 expanding을 취했을때 나오는 그래프 G'도 perfect이다. 라는 명제를 |V(G)|에 대한 induction을 이용해서 보이는거고요. 증명에서는 귀납가정을 H가 G의 어떤 proper induced subgraph K에 그 vertex w에 expanding을 취한 경우에 사용하니까, 결국 명제 P(K,w)를 고려하는거죠. 근데 항상 |V(K)| < |V(G)|니까 고려되는 그래프의 정점수는 줄어들겠죠
제가 이해하고 있는 귀납법은 n = 1(즉 K^1 ) 에서 기준케이스를 증명했으면, 그것에서 출발해야 한다는 게 제 이해에요. 그러니까 저 증명이 vertex set 의 크기에 대해 옳게 induction 을 하려면 non-trivial perfect graph 가 존재하는 vertex set 의 최소크기를 구하고 그게 p 라고 했을 때, p + 1 으로 expanding 하는 모든 경우의 수를 다 따져주어야 case i) 이 비로소 증명된다는게 제 주장입니다요 ㅠㅠ
마찬가지로 P(K,w)를 증명할때 또 귀납가정을 사용해서 K의 어떤 proper induced subgraph K'와 그것의 vertex v'에 대해서 P(K',w')를 고려할 것이고, |V(K')|<|V(K)|를 만족합니다. 결국 recursive하게 고려되는 그래프의 정점수가 줄어들테니 결국 base case (vertex 개수가 하나인 경우) 에 도달하겠죠.
ㅇㅎ 이해했어요 감사합니다!!!!!!
저기서 사용하는건 그냥 명제들 P_1 , P_2 , P_3 , ...이 주어져있을때, [P_1이 참이고, 임의의 i에 대해서 P_1,P_2,..,P_{i-1}이 참일때 P_i도 참이다.]라는 사실을 증명해서 P_1 , P_2 , P_3 , ...이 전부 참이라는걸 증명한것 뿐이에요.
임의의 perfect 그래프 G와 그것의 임의의 vertex v에 대해서 pair (G,v)를 고려할때, 이 pair들을 |V(G)|의 크기 순으로 나열한걸 (G_1,v_1),(G_2,v_2),...로 둘 수 있고 그래프는 finite하니 이것들은 항상 countable하죠. 따라서 명제 P_i를 P(G_i,v_i) : perfect 그래프 G_i에 대해서 v_i를 expanding한 그래프 또한 perfect이다. 로 정할때 P_1 , P_2 , P_3 , ...이 전부 참이라는걸 이런 방식으로 증명한 겁니다.
근데 Diestel 책에서 이런 방식의 수학적귀납법은 Chapter 5 이전에도 꽤 있었을것이고 기초해석학 시간에도 이런 strong induction 많이 사용하지 않나요?
그리고 실제로 perfect graph G가 주어졌을때, G의 임의의 vertex v에 대해서 v를 임의의 perfect graph H로 치환했을때 (V(H)와 V(G)가 disjoint하다는 전제하에서, G에서 v를 제거하고, V(H)의 원소들을 더하고, v와 인접한 vertex들은 모두 V(H)와 인접하게끔 만든 그래프), 이렇게 만들어진 그래프도 perfect이라는 lemma가 있어요. (Replacement lemma) 본문의 lemma는 이 replacement lemma의 특별한 경우, 그냥 vertex를 K_2로 치환한 경우에 perfectness가 유지된다는걸 보인것 뿐입니다.. (K_2가 perfect인건 자명하니까요)
http://web.math.ucsb.edu/~padraic/mathcamp_2011/perfectgraphs/MC2011_perfectgraphs_wk1_day4.pdf
이 lecture note에 replacement lemma 증명이 있고 (Theorem 2) 증명 아이디어는 거의 같다고 보심 됩니다.
그리고 perfect graph에 관심이 있으면 이를 주제로 다룬 멋진 survey가 있습니다.
https://arxiv.org/pdf/1301.5149.pdf
흐어어어...언제다보지...너무 감사드려요 ㅠㅠㅠㅠ - dc App