해바라기 (수학)

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

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

정의

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

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

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

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

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

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

성질

수

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

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

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

증명:

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

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

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

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

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

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

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

이다.

해바라기 정리

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

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

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

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

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

예

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

역사

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

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

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