방청소를 하다가 영재고 대비 시절의 교재를 발견했다. 그 교재 마지막 장에 과하게 졸려보이는 글씨로(...) 이 정리와 증명이 쓰여 있길래 대충 재구성해본다. 이걸 조사하면서 Sperner를 슈페르너로 읽는다는 걸 처음 알았다. 지금까지 스퍼너로 읽었는데 ㅁㄴㅇㄹ Definition. (Sperner Family) \([n] := \{1,2,\cdots n\}\)이라 할 때, \(\mathcal{F} \subset 2^{[n]}\)가 임의의 두 원소 \(A, B \in \mathcal{F}\)에 대해 \(A \subset B \Leftrightarrow A = B\)를 만족할 때 \(\mathcal{F}\)를 \([n]\)의 Sperner Family라고 한다. 즉 \(\subset\)을 순서관계로 생각..

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

시험기간인데 포스팅은 하고 싶어서 내뱉는 짧은 주제.이산수학이 맞는지는 모르겠지만... 이것과 연관된 이산수학 문제가 하나 있으니까 이 카테고리에 포스팅하기로 한다. 1. Definition of Beatty Sequence 양의 무리수 \(r\)에 대해서 Beatty Sequence \(\mathcal{B}_r\)을 다음과 같이 정의한다. $$ \mathcal{B}_r := \{ \lfloor r \rfloor, \lfloor 2r \rfloor, \cdots, \lfloor nr \rfloor \cdots \} $$ 2. Rayleigh's theorem 두 양수 무리수 \(r,s\)가 \(\frac{1}{r}+\frac{1}{s} = 1\)을 만족할 때, \(\mathcal{B}_r\)과 \(\ma..