해바라기 (수학) 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:ABC Venn Diagram.svg|섬네일|right|이 [[벤 다이어그램]]에서, 만약 <math>AB=BC=AC=\varnothing</math>이라면 이는 해바라기를 이룬다. 그러나 <math>ABC=\varnothing</math>일 필요는 없다.]]
[[집합론]]과 [[조합론]]에서 '''해바라기'''({{llang|en|sunflower}})는 서로 다른 두 원소의 [[교집합]]이 항상 일정한 [[집합족]]이다.

== 정의 ==
[[부분 순서 집합]] <math>P</math>가 [[만남 반격자]]라고 하자 (즉, 임의의 두 원소에 대하여 그 [[하한]] <Math>a\land b</math>이 존재한다고 하자). <math>P</math> 속의 [[부분 집합]] <math>A\subseteq P</math>가 다음 조건을 만족시킨다면, '''하향 해바라기'''({{llang|en|downward sunflower}})라고 한다.<ref>{{저널 인용|제목=Sunflowers in Lattices|이름=Geoffrey|성=McKenna|권=12|날짜=2005|쪽=R66|url=http://www.combinatorics.org/ojs/index.php/eljc/article/view/v12i1r66|저널=The Electronic Journal of Combinatorics|issn=1077-8926|언어=en}}</ref>
:<math>\forall a,b,a',b'\in A\colon (a\ne b,\;a'\ne b'\implies a\land b=a'\land b')</math>
이 경우, <math>\textstyle\bigwedge S\in P</math>는 <math>S</math>의 '''핵'''(核, {{llang|en|kernel, core}})이라고 한다.
마찬가지로, 만약 <math>P</math>가 [[이음 반격자]]일 경우, '''상향 해바라기'''({{llang|en|upward sunflower}})는 다음 조건을 만족시키는 [[부분 집합]] <math>S\subseteq P</math>이다.
:<math>\forall a,b,a',b'\in A\colon (a\ne b,\;a'\ne b'\implies a\lor b=a'\lor b')</math>

집합 <math>S</math> 속의 '''해바라기'''란 [[멱집합]] <math>(\mathcal P(S),\subseteq)</math> 속의 하향 해바라기를 뜻한다.<ref name="Kunen">{{서적 인용|title=Set theory: an introduction to independence proofs|성=Kunen|이름=Kenneth|저자링크=케네스 쿠넌|publisher=North-Holland|날짜=1980|isbn=978-0-444-86839-8|url=http://store.elsevier.com/Set-Theory-An-Introduction-To-Independence-Proofs/K_-Kunen/isbn-9780444868398/|총서=Studies in Logic and the Foundations of Mathematics|권=102|zbl=0534.03026|mr=597342|언어=en|확인날짜=2016-08-10|보존url=https://web.archive.org/web/20160911102401/http://store.elsevier.com/Set-Theory-An-Introduction-To-Independence-Proofs/K_-Kunen/isbn-9780444868398/|보존날짜=2016-09-11|url-status=dead}}</ref>{{rp|49, Definition II.1.4}}<ref name="Jukna">{{서적 인용|제목=Extremal combinatorics with applications in computer science|이름=Stasys|성=Jukna|doi=10.1007/978-3-642-17364-6|총서=Texts in Theoretical Computer Science|issn=1862-4499|판=2|isbn=978-3-642-17363-9|날짜=2011|출판사=Springer-Verlag|zbl=1239.05001|언어=en}}</ref>{{rp|89, §6.1}}
* 임의의 <math>A,B,A',B'\in\mathcal A</math>에 대하여, 만약 <math>A\ne B</math>이며 <math>A'\ne B'</math>이라면, <math>A\cap B=A'\cap B'</math>이다.

== 성질 ==
=== 수 ===
크기 <math>n</math>의 집합 <math>S</math> 위의 해바라기 <math>\mathcal A\subseteq\mathcal P(S)</math>의 수는 다음과 같다.
:<math>2\sum_{k=0}^{n+1}k\left\{{n+1\atop k}\right\}</math>
여기서 <math>\textstyle\left\{{\bullet\atop\bullet}\right\}</math>는 [[제2종 스털링 수]]이다.
<div class="mw-collapsible mw-collapsed toccolours">
'''증명:'''
<div class="mw-collapsible-content">
해바라기에는 항상 그 핵을 추가하거나 제거할 수 있으므로, 총 해바라기의 수는 핵을 원소로 갖지 않는 해바라기들의 수의 2배이다. 따라서, 핵을 원소로 갖지 않는 해바라기의 수를 세자.

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

또한, <math>\mathcal P</math>에서 임의의 원소 <math>Q\in\mathcal P</math>를 고르자.

이제, 이 데이터 <math>(\mathcal P,Q)</math>에 다음과 같은, 핵을 원소로 갖지 않는 해바라기 <math>\mathcal A</math>를 대응시킬 수 있다.
* 만약 <math>\bullet\in Q</math>라면, <math>\mathcal A=\{P\cup Q\setminus\{\bullet\}\colon P\in\mathcal P\}</math>. 그 핵은 <math>Q\setminus\{\bullet\}</math>이다.
* 만약 <math>\bullet\not\in Q</math>이고 <math>\bullet\in R\in\mathcal P</math>라면, <math>\mathcal A=\{P\cup R\setminus\{\bullet\}\colon P\in\mathcal P\setminus\{Q,R\}\}</math>. 그 핵은 <math>R\setminus\{\bullet\}</math>이며, <math>\textstyle Q=S\setminus\bigcup\mathcal A</math>는 해바라기의 "바깥"이다.
따라서, 이러한 데이터 <math>(\mathcal P,Q)</math>의 집합은 핵을 원소로 갖지 않는 해바라기들의 집합과 표준적으로 [[일대일 대응]]한다. 이러한 데이터의 집합의 크기는 물론
:<math>\sum_{k=0}^{n+1}k\left\{{n+1\atop k}\right\}</math>
이다.
</div></div>

=== 해바라기 정리 ===
임의의 두 [[기수 (수학)|기수]] <math>\kappa,\lambda</math>에 대하여, <math>f(\kappa,\lambda)</math>를 다음 조건이 성립하는 최소의 기수 <math>\mu</math>라고 하자. (이러한 <math>\mu</math>가 존재하지 않는다면 <math>f(\kappa,\lambda)=\infty</math>로 놓자.)
* 임의의 집합 <math>S</math> 및 그 속의 [[집합족]] <math>\mathcal A\subseteq\mathcal P(S)</math>에 대하여, 만약 모든 <math>A\in\mathcal A</math>에 대하여 <math>|A|<\kappa</math>이며, <math>|\mathcal A|\ge\mu</math>라면, 임의의 기수 <math>\alpha<\lambda</math>에 대하여 <math>\mathcal A</math> 속에는 [[집합의 크기|크기]] <math>\alpha</math>의 해바라기 <math>\mathcal B\subseteq\mathcal A</math>가 존재한다.

다음과 같은 성질이 알려져 있다.
* <math>1\le\kappa<\aleph_0</math>, <math>2\le\lambda<\aleph_0</math>라면, <math>f(\kappa,\lambda)\le(\kappa-1)!(\lambda-2)^{\kappa-1}+1</math>이다.<ref name="ER">{{저널 인용 | last1=Erdős | first1=Paul |authorlink1=에르되시 팔| last2=Rado | first2=Richard |author2-link=리하르트 라도| title=Intersection theorems for systems of sets | doi=10.1112/jlms/s1-35.1.85  |mr=0111692 | year=1960 | journal=Journal of the London Mathematical Society| issn=0024-6107 | volume=35 | issue=1 | pages=85–90 | url=https://www.renyi.hu/~p_erdos/1960-04.pdf | 언어=en}}</ref><ref name="Jukna"/>{{rp|89–90, §6.1}}
* <math>f(\aleph_0,\aleph_2)=\aleph_1</math>이다.<ref name="Kunen"/>{{rp|49, Theorem II.1.5}}
* 만약 <math>\aleph_0\le\kappa<\theta</math>이며, <math>\theta</math>가 [[정칙 기수]]이며, 임의의 <math>\alpha<\theta</math>에 대하여 <math>|\alpha^{<\kappa}|<\theta</math>일 경우, <math>f(\kappa,\theta^+)=\theta</math>이다.<ref name="Kunen"/>{{rp|49, Theorem II.1.6}}
* 자명하게, <math>\lambda\le f(\kappa,\lambda)^+</math>이다. (이는 집합족은 스스로보다 더 큰 해바라기를 포함할 수 없기 때문이다.)
* 자명하게, 임의의 기수 <math>\kappa</math>에 대하여 <math>1\le\lambda\le3</math>일 경우, <math>f(\kappa,\lambda)=\lambda-1</math>이다. (이는 크기가 2 이하인 집합족은 항상 해바라기이기 때문이다.) 물론 <math>f(\kappa,0)=0</math>이다.
* 자명하게, 만약 <math>\kappa\le\kappa'</math>이라면 <math>f(\kappa,\lambda)\le f(\kappa',\lambda)</math>이다. 마찬가지로, 만약 <math>\lambda\le\lambda'</math>이라면 <math>f(\kappa,\lambda)\le f(\kappa,\lambda')</math>이다.
이와 같은, <math>f(\kappa,\lambda)</math>에 대한 상계·하계들을 '''해바라기 정리'''({{llang|en|sunflower theorem}})라고 한다.

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

== 역사 ==
[[파일:Mediawiki_logo_sunflower.svg|섬네일|right|"해바라기"라는 용어는 식물 [[해바라기]]의 [[꽃차례]]에 비유한 것이다.]]
1980년에 [[에르되시 팔]]과 [[리하르트 라도]]가 유한 해바라기에 대한 해바라기 정리를 증명하였다.<ref name="ER"/> 에르되시와 라도는 해바라기를 "델타 계"(Δ界, {{llang|en|Δ-system}})라고 불렀다.

"해바라기"({{llang|en|sunflower}})라는 용어는 적어도 1981년부터 사용되기 시작하였다.<ref>{{저널 인용 | last1=Deza | first1=Michael | last2=Frankl | first2=Péter | title=Every large set of equidistant (0, +1, −1)-vectors forms a sunflower | doi=10.1007/BF02579328 |mr=637827 | year=1981 | journal=Combinatorica | issn=0209-9683 | volume=1 | issue=3 | pages=225–231|언어=en}}</ref> "해바라기"라는 용어는 식물 [[해바라기]]의 [[꽃차례]]에 비유한 것이다. 이는 (유한) 해바라기의 [[벤 다이어그램]]을 대칭적으로 그리면, 이는 마치 [[꽃]]과 유사하기 때문이다. 구체적으로, [[해바라기]]의 [[꽃차례]]는 중심의 갈색의 작은 관꽃들과, 이를 둘러싸는 노랗고 길쭉한 혀꽃들로 구성되어 있다. (흔히, 후자를 "꽃잎"으로 일컫는다.) 이 비유에서, 수학적 해바라기의 핵은 관꽃들의 집합에 해당하며, 수학적 해바라기의 각 원소는 모든 관꽃들의 집합과 하나의 혀꽃으로 구성된다.

== 참고 문헌 ==
{{각주}}

== 외부 링크 ==
* {{웹 인용|url=http://michaelnielsen.org/polymath1/index.php?title=The_Erdos-Rado_sunflower_lemma|제목=The Erdos-Rado sunflower lemma|웹사이트=Polymath|언어=en}}
* {{웹 인용|url=http://theoryapp.com/the-erdos-rado-sunflower-lemma/|제목=The Erdos-Rado sunflower lemma|웹사이트=TheoryApp|날짜=2013-11-06|언어=en}}
* {{웹 인용|url=https://kintali.wordpress.com/2009/07/15/the-sunflower-lemma/|제목=The sunflower lemma|웹사이트=My Brain is Open|이름=Shiva|성=Kintali|날짜=2009-07-15|언어=en}}

{{전거 통제}}

[[분류:집합론]]
[[분류:조합론]]