HGHC는 graph theory / combinatorics에서 오랫동안 제기되어 왔던 추측을 반증하는 lemma로, 확률론적 방법의 대표적인 예제이다. 확률론적 방법의 진수를 보여주는 lemma라고 생각하는데, 확률론적 방법 전체를 소개하기에는 너무 길고, 이 정리의 증명만 포스트에 싣기로 한다. 아마 wikipedia 수준의 사전 지식 이외에는 필요하지 않을 것이다. Thanks to. claim 0. Introduction 임의의 자연수 t, ut, \ ut, u에 대해 g(G)>tg(G) > tg(G)>t와 χ(G)>u\chi (G) > uχ(G)>u를 동시에 만족하는 그래프 GGG가 존재한다. 여기서 그래프의 girth g(G)g(G)g(G)는 GGG에서 가장 작은 cycle의 크기를 의미하고, χ(G)\chi (G)χ(G)의 경우 g..

안녕하세요 탐레프입니다!첫 포스팅을 뭘로 할까 고민하다가, 시간도 없고 해서 그냥 간단한 문풀 포스팅을 하려고 해요. 아직 LaTeX를 못 익혀서 결국 다음 수식편집기로 하겠지만요...라고 다짐하다가 다음 수식편집기가 펑하고 터져서 결국 모르는 텍을 부랴부랴 배워서 포스팅했습니다. 그 때문에 가독성은... 광팡팡...텍 익히고 고칠게요.------------------------------------------------------------------------------------ 문제는 다음과 같습니다! "교실에 n명의 학생이 있다. 이 때 각 학생은 10명 또는 11명의 친구를 가지고 있으며, 아무렇게나 두 학생을 잡았을 때 그들과 공통으로 친구인 학생이 정확히 5명 있다. 이 때 가능한 학생의 ..