Cube를 2색으로 칠할 수 있다.

병맛 넘치는 연습문제를 풀어본 기념으로 이를 포스팅.

이번 포스팅에서는, 정말로 쉽게 알 수 있는, Cube를 2색으로 칠할 수 있음을 증명할 것이다.

n-cube 은 를 점의 집합으로 가지고, 하나의 좌표만 다른 두 점의 쌍에 대해 간선을 가지는 그래프를 말한다.

의 점들을 2색으로 칠할 수 있다는 것은 매우 쉽게 알 수 있다. 인접한 두 점끼리는 1 좌표의 갯수가 홀짝으로 갈리게 되므로 값이 1인 좌표의 갯수를 세서 짝수이면 붉은색, 홀수이면 파란색으로 칠하면 된다.

그러나 오늘 다룰 증명에서는 이 쉽게 증명가능한 사실을 약간 다른 각도에서 쓸데없이 복잡한 방법을 사용해서 보일 것이다.

Nesbitt의 부등식, Shapiro의 부등식

심심풀이로 풀어보았던 Cauchy-Schwarz Master Class의 연습문제의 풀이나 올려본다.

아마 수학 경시하셨던 분들이라면 다들 쉽게 풀었을만한 문제들… 뭐 그러나 난 수학 전공자가 아니라서 (…)

첫 부등식은 다음과 같이 대칭적으로 생겨먹은, Nesbitt의 부등식이란 이름을 달고 있는 것이다.

2010년 TCS 분야 연말 결산

2010년도 이제 몇 시간 안 남았네. 올해도 뭘 한건지…;;;

매해 그렇지만, 올해는 특히 많은 굵직한 문제들에서 큰 진보가 있었던 한 해가 아니었나 싶다. 특히 수십년간 답을 알 수 없었던 문제들에서 진전이 있었던 것이 인상적.

올해 나름대로 인상적인 결과들을 다음과 같이 정리해보았다.

Combinatorics in Statistical Physics : Open Problems

지난 2달간 참석한 윈터스쿨에서 가장 인상적이고 도움이 될만한 코스는 뜻밖에도 통계 물리에서의 조합론 코스였습니다. 사실 가장 기대를 안 한 코스였는데 막상 들어보니 의외로 고전적인 조합론 및 이론 전산학에 관련된 내용이었습니다.

또한 몇몇 인상적이고 좋은 미해결 문제들을 알게 되어서 여기에 포스팅 해드립니다. 읽어보시면 아시겠지만 푸는데는 물리적 백그라운드가 전혀 필요하지 않습니다.

증명은 최대한 생략하겠습니다. 사실 잘 몰랏

지난 두 달 반 동안 유럽에 다녀왔습니다

프랑스, 독일에서 열린 워크샵과 윈터(?) 스쿨에 참가하고 돌아왔습니다.

나름 험난한 일정이었네요. 후… 살아돌아온게 다행.

뭐 그러나 나름 유익한 시간이었던 것 같기도 합니다. 사실 현실 도피

뭔가 중구난방인듯한, 제가 참여한 이벤트들은 다음과 같습니다.

Weak Perfect Graph Conjecture의 몇가지 증명 (3) – Polyhedral Method

지난 포스팅 이후 한 달을 훌쩍 넘겨 네번째 포스팅…;;; 이번에는 Polyhedral method를 이용한 증명을 다루어보도록 하겠다.

이 polyhedral method의 고향은 조합적 최적화(Combinatorial optimization)라 불리는 조합론의 한 분야이다. 조합적 최적화는  ‘어떤 특징을 가지는 유한한 객체 중 최적의 해는 무엇인가?’와 같은 물음을 다루는 분야이다. 중요 키워드는 ‘유한한’, 그리고 ‘최적’. 조합론에서 다루는 구조들이 셀 수 있는 유한한 구조라는 것을 상기해보면 이 분야의 수식어에 왜 ‘조합적’이 붙는지 납득할만하다. 아니 사실 그보다도 조합론 연구자들이 크게 기여를 했었기 때문이겠지만.

조합적 최적화 문제의 전형적인 예로써 maximum matching 문제를 생각할 수 있다. 그래프 의 matching 은 서로 vertex들을 공유하지 않는 의 edge들의 집합을 말한다. 이 때 ‘maximum matching 문제는 최대의 크기를 가지는 matching은 무엇인가?’를 묻는다.

P != NP 증명을 둘러싼 소동에 대한 단상

이미 다들 잘 아시겠지만 HP Lab의 연구원 Vinay Deolalikar가 지난 8월 6일 P != NP를 증명한 결과를 그의 홈페이지에 올렸다. 이 P vs NP 문제는 Clay 재단의 100만 달러가 걸린 7문제 중 하나로 대중에게도 잘 알려져 있다. 참고로 그 중 하나인 푸앙카레의 추측은 Grigory Perelman에 의해 이미 풀린 상태.

어찌됐건 유명해졌다.

P vs NP 문제를 간단하게 설명하면, 이 문제는 아직까지 효율적인 알고리즘을 찾아내지 못한 NP-Complete라 불리는 문제들에 대한 효율적인 알고리즘이 존재하는가, 아닌가에 대한 물음이다. 지난 수십년간 많은 이론 전산학자들이 이 문제를 풀려고 노력해왔고 그 노력으로 이론 전산학이란 연구 분야가 지금껏 성장해왔다. 그러니까, P vs NP 문제는 조금 비약하면 이론 전산학 전체를 떠받드는 가장 중요하고 어려운 문제인셈.

요즘 취미로 공부하는 책들

당장의 연구와 관련없는 진행 중인 공부리스트. 이렇게 포스팅을 해야 근성있게 끝내겠지 (…)

1. Introduction Enumerative Combinatorics by Miklos Bona

Enumerative combinatorics는 퍼즐 푼다는 느낌으로 공부. Stanley의 책이 유명한 것 같은데 그건 이걸 다 보고서나…

2. Algebra by Hungerford

Fraleigh를 대충 독학하긴 했지만 좀 더 심화된 내용을 알고 싶어서 사실 다 까먹어서 공부중.

3. Introduction to Real Analysis by Trench

해석학은 예전에 대충 들어뒀는데 제대로 알아야 할 필요성을 점차 절감하고 있다. (아니 왜?)

4. Game Theory by Myerson

게임 이론은 요즘 이론 전산학에서 뜨고 있는 분야이기도 하니까… (Algorithmic Game Theory) AGT를 공부하기 전에 일단 정통 게임 이론부터 공부. 역시 경제학 교재는 읽기 쉬워

뭔가 이렇게 포스팅했으니 끝낼 수 있겠지 (…)

Weak Perfect Graph Conjecture의 몇가지 증명 (2)

대략 10일여만에 포스팅… 블로그는 역시 귀찮아…-_-;;;

아무튼, 이번 포스팅에서는 약속한대로 선형대수를 이용한 Perfect graph 정리의 증명을 다룰 것이다. 이 증명은 또한 Perfect graph 정리의 다른 버전에 대한 것이다. 아마 내 기억이 맞다면 그래프 이론을 두 번 들었을때(수강, 청강) 모두 이 증명을 배웠던듯?

Weak Perfect Graph Conjecture의 몇가지 증명 (1)

이제 본격적으로 WPC의 증명에 대해 살펴보기로하자….를 하기 전에 지난번에 허접하게 언급한 WPC를 본래 추측된 형태에 따라 다시 설명하도록 하겠다.

앞서 포스팅에서 정의한 것과 같이 clique number를 그래프 의 최대 clique의 크기라 하고 로 나타낸다. Chromatic number를 그래프 의 색칠에 필요한 색의 최고 갯수라 하고 이를 라고 하자. (갑자기 영어를 쓰는 것은 한글 용어가 영 생경해서…;;;) 그러면, 적어도 clique의 크기만큼 색이 필요하므로 가 되는 것을 알 수 있다.

이 때 의 모든 induced subgraph 에 대해서 가 성립하는 그래프를 -perfect라고 하자. 용어가 전과는 약간 다른데 그 이유는 나중에…

여기서 두 가지 특성을 더 정의한다. 어떤 그래프의 vertex subset에서 그 안의 어떤 vertex 에 대해서도 이들을 연결하는 edge가 없는 경우 이를 independent하다고 하자. Independence number는 independent한 가장 큰 subset의 크기를 나타낸다. 이것을라 하자.