해바라기 (수학)

이 벤 다이어그램에서, 만약 $AB=BC=AC=\varnothing$이라면 이는 해바라기를 이룬다. 그러나 $ABC=\varnothing$일 필요는 없다.

집합론과 조합론에서 해바라기(영어: sunflower)는 서로 다른 두 원소의 교집합이 항상 일정한 집합족이다.

정의

부분 순서 집합 $P$가 만남 반격자라고 하자 (즉, 임의의 두 원소에 대하여 그 하한 $a\land b$이 존재한다고 하자). $P$ 속의 부분 집합 $A\subseteq P$가 다음 조건을 만족시킨다면, 하향 해바라기(영어: downward sunflower)라고 한다.

$\forall a,b,a',b'\in A\colon (a\neq b,\;a'\neq b'\implies a\land b=a'\land b')$

이 경우, $\textstyle \bigwedge S\in P$는 $S$의 핵(核, 영어: kernel, core)이라고 한다. 마찬가지로, 만약 $P$가 이음 반격자일 경우, 상향 해바라기(영어: upward sunflower)는 다음 조건을 만족시키는 부분 집합 $S\subseteq P$이다.

$\forall a,b,a',b'\in A\colon (a\neq b,\;a'\neq b'\implies a\lor b=a'\lor b')$

집합 $S$ 속의 해바라기란 멱집합 $({\mathcal {P}}(S),\subseteq )$ 속의 하향 해바라기를 뜻한다.^{:49, Definition II.1.4:89, §6.1}

• 임의의 $A,B,A',B'\in {\mathcal {A}}$에 대하여, 만약 $A\neq B$이며 $A'\neq B'$이라면, $A\cap B=A'\cap B'$이다.

성질

수

크기 $n$의 집합 $S$ 위의 해바라기 ${\mathcal {A}}\subseteq {\mathcal {P}}(S)$의 수는 다음과 같다.

$2\sum _{k=0}^{n+1}k\left\{{n+1 \atop k}\right\}$

여기서 $\textstyle \left\{{\bullet \atop \bullet }\right\}$는 제2종 스털링 수이다.

증명:

해바라기에는 항상 그 핵을 추가하거나 제거할 수 있으므로, 총 해바라기의 수는 핵을 원소로 갖지 않는 해바라기들의 수의 2배이다. 따라서, 핵을 원소로 갖지 않는 해바라기의 수를 세자.

$S$에 새 원소 $\bullet$를 추가한 집합 $S_{\bullet }=S\sqcup \{\bullet \}$의, $0\leq k\leq n+1$ 조각으로의 분할 ${\mathcal {P}}$를 생각하자. 그 가짓수는 제2종 스털링 수 $\textstyle \{{n+1 \atop k}\}$이다.

또한, ${\mathcal {P}}$에서 임의의 원소 $Q\in {\mathcal {P}}$를 고르자.

이제, 이 데이터 $({\mathcal {P}},Q)$에 다음과 같은, 핵을 원소로 갖지 않는 해바라기 ${\mathcal {A}}$를 대응시킬 수 있다.

• 만약 $\bullet \in Q$라면, ${\mathcal {A}}=\{P\cup Q\setminus \{\bullet \}\colon P\in {\mathcal {P}}\}$. 그 핵은 $Q\setminus \{\bullet \}$이다.
• 만약 $\bullet \not \in Q$이고 $\bullet \in R\in {\mathcal {P}}$라면, ${\mathcal {A}}=\{P\cup R\setminus \{\bullet \}\colon P\in {\mathcal {P}}\setminus \{Q,R\}\}$. 그 핵은 $R\setminus \{\bullet \}$이며, $\textstyle Q=S\setminus \bigcup {\mathcal {A}}$는 해바라기의 "바깥"이다.

따라서, 이러한 데이터 $({\mathcal {P}},Q)$의 집합은 핵을 원소로 갖지 않는 해바라기들의 집합과 표준적으로 일대일 대응한다. 이러한 데이터의 집합의 크기는 물론

$\sum _{k=0}^{n+1}k\left\{{n+1 \atop k}\right\}$

이다.

해바라기 정리

임의의 두 기수 $\kappa ,\lambda$에 대하여, $f(\kappa ,\lambda )$를 다음 조건이 성립하는 최소의 기수 $\mu$라고 하자. (이러한 $\mu$가 존재하지 않는다면 $f(\kappa ,\lambda )=\infty$로 놓자.)

• 임의의 집합 $S$ 및 그 속의 집합족 ${\mathcal {A}}\subseteq {\mathcal {P}}(S)$에 대하여, 만약 모든 $A\in {\mathcal {A}}$에 대하여 $|A|<\kappa$이며, $|{\mathcal {A}}|\geq \mu$라면, 임의의 기수 $\alpha <\lambda$에 대하여 ${\mathcal {A}}$ 속에는 크기 $\alpha$의 해바라기 ${\mathcal {B}}\subseteq {\mathcal {A}}$가 존재한다.

다음과 같은 성질이 알려져 있다.

• $1\leq \kappa <\aleph _{0}$, $2\leq \lambda <\aleph _{0}$라면, $f(\kappa ,\lambda )\leq (\kappa -1)!(\lambda -2)^{\kappa -1}+1$이다.^{:89–90, §6.1}
• $f(\aleph _{0},\aleph _{2})=\aleph _{1}$이다.^{:49, Theorem II.1.5}
• 만약 $\aleph _{0}\leq \kappa <\theta$이며, $\theta$가 정칙 기수이며, 임의의 $\alpha <\theta$에 대하여 $|\alpha ^{<\kappa }|<\theta$일 경우, $f(\kappa ,\theta ^{+})=\theta$이다.^{:49, Theorem II.1.6}
• 자명하게, $\lambda \leq f(\kappa ,\lambda )^{+}$이다. (이는 집합족은 스스로보다 더 큰 해바라기를 포함할 수 없기 때문이다.)
• 자명하게, 임의의 기수 $\kappa$에 대하여 $1\leq \lambda \leq 3$일 경우, $f(\kappa ,\lambda )=\lambda -1$이다. (이는 크기가 2 이하인 집합족은 항상 해바라기이기 때문이다.) 물론 $f(\kappa ,0)=0$이다.
• 자명하게, 만약 $\kappa \leq \kappa '$이라면 $f(\kappa ,\lambda )\leq f(\kappa ',\lambda )$이다. 마찬가지로, 만약 $\lambda \leq \lambda '$이라면 $f(\kappa ,\lambda )\leq f(\kappa ,\lambda ')$이다.

이와 같은, $f(\kappa ,\lambda )$에 대한 상계·하계들을 해바라기 정리(영어: sunflower theorem)라고 한다.

예

크기 2 이하의 집합족은 항상 (자명하게) 해바라기이다. 짝마다 서로소 집합족(즉, 서로 다른 두 원소가 항상 서로소인 집합족)은 (핵이 공집합인) 해바라기이다.

역사

"해바라기"라는 용어는 식물 해바라기의 꽃차례에 비유한 것이다.

1980년에 에르되시 팔과 리하르트 라도가 유한 해바라기에 대한 해바라기 정리를 증명하였다. 에르되시와 라도는 해바라기를 "델타 계"(Δ界, 영어: Δ-system)라고 불렀다.

"해바라기"(영어: sunflower)라는 용어는 적어도 1981년부터 사용되기 시작하였다. "해바라기"라는 용어는 식물 해바라기의 꽃차례에 비유한 것이다. 이는 (유한) 해바라기의 벤 다이어그램을 대칭적으로 그리면, 이는 마치 꽃과 유사하기 때문이다. 구체적으로, 해바라기의 꽃차례는 중심의 갈색의 작은 관꽃들과, 이를 둘러싸는 노랗고 길쭉한 혀꽃들로 구성되어 있다. (흔히, 후자를 "꽃잎"으로 일컫는다.) 이 비유에서, 수학적 해바라기의 핵은 관꽃들의 집합에 해당하며, 수학적 해바라기의 각 원소는 모든 관꽃들의 집합과 하나의 혀꽃으로 구성된다.

외부 링크

• “The Erdos-Rado sunflower lemma”. 《Polymath》 (영어). 
• “The Erdos-Rado sunflower lemma”. 《TheoryApp》 (영어). 2013년 11월 6일. 
• Kintali, Shiva (2009년 7월 15일). “The sunflower lemma”. 《My Brain is Open》 (영어).