슈페르너 정리

스페르너 정리는 이산 수학에서 유한 집합의 가능한 가장 큰 가군을 설명하며, 가군 중 어떤 다른 집합도 포함하지 않습니다. 그것은 극한 집합 이론의 중심 결과 중 하나입니다. 그것은 1928년에 그것을 출판한 에마누엘 스페르너의 이름을 따서 지어졌습니다.

이 결과는 때때로 슈페르너의 보조정리라고 불리지만, "슈페르너의 보조정리"라는 이름은 삼각형을 색칠하는 것과 관련이 없는 결과를 가리키기도 합니다. 두 결과를 구별하기 위해 슈페르너 가군의 크기에 대한 결과는 이제 슈페르너 정리로 더 일반적으로 알려져 있습니다.

진술

어떤 집합도 다른 집합의 엄격한 부분 집합이 아닌 집합의 계열을 스페르너 계열 또는 집합의 안티체인 또는 클러터라고 합니다. 예를 들어, n-요소 집합의 k-요소 부분집합의 족은 스페르너 가군입니다. 포함 집합은 포함 집합이 포함하는 집합보다 엄격하게 커야 하고 이 집합에서 모든 집합의 크기가 동일해야 하므로 이 집합에는 다른 집합이 포함될 수 없습니다. 이 예제를 가능한 한 많은 집합을 갖는 k의 값은 n이 짝수이면 n/2, n이 홀수이면 n/2에 가장 가까운 정수 중 하나입니다. 이 선택의 경우 패밀리의 집합 수는 ${\tbinom {n}{\lfloor n/2\rfloor }}$ ( ${\tbinom {n}{\lfloor n/2\rfloor }}$ ⌊ ${\tbinom {n}{\lfloor n/2\rfloor }}$ n / $2$ ⌋) ${\displaystyle$ {\ $tbinom {$ n}{\lfloor ${\tbinom {n}{\lfloor n/2\rfloor }}$ n/2\rfloor}}입니다.

스페르너 정리는 이 예들이 n개 원소 집합에 대해 가능한 가장 큰 스페르너 가군이라는 것을 말합니다. 공식적으로 정리하면,

결합이 총 n개의 원소를 갖는 모든 스페르너 가군 S에 대하여, $S$ $|S|\leq {\binom {n}{\lfloor n/2\rfloor }},$ ( $|S|\leq {\binom {n}{\lfloor n/2\rfloor }},$ ⌊ $n$ / $|S|\leq {\binom {n}{\lfloor n/2\rfloor }},$ 2 $|S|\leq {\binom {n}{\lfloor n/2\rfloor }},$ ⌋), {\ $displaystyle S \leq$ {\ $binom {n$ }{\lfloor $|S|\leq {\binom {n}{\lfloor n/2\rfloor }},$ n/2\rfloor}},
S가 $\lfloor n/2\rfloor$ ⌊ $n$ / $2$ $\lceil n/2\rceil$ ⌋ ${\displaystyle \lfloor$ n / 2\rfloor} 또는 $크기$ ⌈ $\lceil n/2\rceil$ {\displaystyle \lceil n / 2\rceil}인 $모든$ 집합의 부분집합으로 구성된 경우에만 동일성이 유지됩니다.

부분주문

슈페르너의 정리는 부분 순서 폭으로도 표현할 수 있습니다. n-요소 집합의 모든 부분집합의 족(그 멱집합)은 집합 포함에 의해 부분적으로 정렬될 수 있습니다. 이 부분 순서에서 두 개의 서로 다른 요소는 둘 다 다른 요소를 포함하지 않을 때 비교할 수 없다고 합니다. 부분 순서의 폭은 쌍으로 비교할 수 없는 원소들의 집합인 반사슬에서 가장 많은 원소들입니다. 이 용어를 집합의 언어로 번역하면, 안티체인은 단지 스페르너 계열이고, 부분 순서의 폭은 스페르너 계열의 최대 집합 수이다. 따라서 슈퍼너 정리를 기술하는 다른 방법은 ${\binom {n}{\lfloor n/2\rfloor }}$ 의 포함 순서의 폭이 ${\binom {n}{\lfloor n/2\rfloor }}$ ( ${\binom {n}{\lfloor n/2\rfloor }}$ ⌊ $n$ / $2$ ⌋) ${\displaystyle$ {\ $binom {n}{\$ lfloor ${\binom {n}{\lfloor n/2\rfloor }}$ n/2\rfloor}}라는 것입니다.

등급화된 부분 순서 집합은 가장 큰 반사슬 중 하나가 모두 같은 순위를 갖는 원소들의 집합에 의해 형성될 때 스페르너 성질을 갖는다고 합니다. 이 용어에서 슈퍼너 정리는 부분 순서화된 유한 집합의 모든 부분 집합들의 부분 순서화된 집합은 집합 포함에 의해 부분 순서화된 슈퍼너 속성을 갖는다는 것을 말합니다.

증명

Sperner의 정리는 많은 증명이 있으며, 각각 다른 일반화로 이어집니다(Anderson(1987) 참조).

다음의 증명은 Lubell(1966)에 의한 것입니다. k-set의 수를 S로 표시합니다_k. For all 0 ≤ k ≤ n,

{n \lfloor {n/2}\rfloor}\geq {n \선택 k}

따라서,

{s_{k} \ over {n \lfloor {n/2}\rfloor}}\leq {s_{k} \over {n \choose k}}

S는 반쇄이므로 위의 부등식을 k = 0에서 n까지 합산한 다음 LYM 부등식을 적용하여 구하면 됩니다.

\sum _{k=0}^{s_{k} \over {n \lfloor {n/2}\rfloor}}\leq \sum _{k=0}^{s_{k} \over {n \선택 k}\leq 1,

그 말은

S =\sum _{k=0}^{n}s_{k}\leq {n \choose \lfloor {n/2}\rfloor }.

이것으로 파트 1의 증명이 완료되었습니다.

동등성을 가지려면 앞의 증명에 있는 모든 부등식이 동등해야 합니다. 부터

{n \lfloor {n/2}\rfloor}={n \선택 k}

if and only if $k=\lfloor {n/2}\rfloor$ or $\lceil {n/2}\rceil ,$ we conclude that equality implies that S consists only of sets of sizes $\lfloor {n/2}\rfloor$ or ${\displaystyle \lceil {n/2}\rceil .$ $}$ 2부의 증명을 끝내는 경우에도 $\lceil {n/2}\rceil.$ 말입니다.

이상하게도 할 일이 더 있는데, 이것은 복잡하기 때문에 여기서 생략합니다. Anderson (1987), 3-4쪽 참조.

일반화

P ${\mathcal {P}}(E),$ E)의 부분집합 ${\displaystyle {\mathcal {P}}(E),$ E의 모든 부분집합에 ${\mathcal {P}}(E),$ 대한 슈퍼너 정리의 몇 가지 일반화가 있습니다.

긴 체인 없음

$\{S_{0},S_{1},\dots ,S_{r}\}\subseteq {\mathcal {P}}(E)$ 은 $완전히$ $S_{0}\subset S_{1}\subset \dots \subset S_{r}$ 된 $,$ $S_{0}\subset S_{1}\subset \dots \subset S_{r}$ $S_{0}\subset S_{1}\subset \dots \subset S_{r}$ $S_{0}\subset S_{1}\subset \dots \subset S_{r}$ ⊂ S $1$ $\{S_{0},S_{1},\dots ,S_{r}\}\subseteq {\mathcal {P}}(E)$ ⊂ ⋯ ⊂ S {\ $displaystyle \{0},$ {1 $},\dots,$ S_{ $r}\}\subseteq {\mathcal$ {P}}(E)}이다 $S_{0}\subset S_{1}\subset \dots \subset S_{r}$ 즉, S $S_{0}\subset S_{1}\subset \dots \subset S_{r}$ 0 $S_{0}\subset S_{1}\subset \dots \subset S_{r}$ ⊆ S 1 ⊂ ⋯ ⊂ $S {\displaystyle S_{$ 0}\ $subset$ S_{1}\ $\{S_{0},S_{1},\dots ,S_{r}\}\subseteq {\mathcal {P}}(E)$ \subset S_{r $\{S_{0},S_{1},\dots ,S_{r}\}\subseteq {\mathcal {P}}(E)$ 아마도 번호를 다시 매긴 후에). 체인의 구성원은 r + 1이며 길이는 r입니다. r-사슬 자유 가군(r-家群, r-家群)은 길이가 r인 사슬을 포함하지 않는 E의 부분집합들의 가군입니다. Erd ő스(1945)는 r-체인이 없는 패밀리의 가장 큰 크기가 가장 큰 이항 ${\binom {n}{i}}$ 의 합임을 증명했습니다 $(ni$ ). ${\displaystyle$ n}{i}}. 대소문자 r = 1은 스페르너 정리입니다.

집합의 p-compos 조건

E의 부분집합 p-쌍의 ${\mathcal {P}}(E)^{p}$ $($ p {\ $displaystyle {\mathcal {P}}(E$ )^{p $}$ 에서, 우리는 p-쌍 $(S_{1},\dots ,S_{p})$ $(S_{1},\dots ,S_{p})$ $(S_{1},\dots, S_{p}$ 는 $(S_{1},\dots,S_{p})$ ≤ 다른 것, $(T_{1},\dots ,T_{p}),$ ( $(T_{1},\dots ,T_{p}),$ $(T_{1},\dots ,T_{p}),$ ${\displaystyle (T_{1},\dots, T_{p}),$ $}$ if $S_{i}\subseteq T_{i}$ for each i = 1,2,...,p. We call $(S_{1},\dots ,S_{p})$ a p-composition of E if the sets $S_{1},\dots ,S_{p}$ form a partition of E. Meshalkin(1963)은 p-구성의 항체인의 최대 크기가 가장 큰 p-다항 계수 ${\binom {n}{n_{1}\ n_{2}\ \dots \ n_{p}}},$ ${\binom {n}{n_{1}\ n_{2}\ \dots \ n_{p}}},$ 1 n ${\binom {n}{n_{1}\ n_{2}\ \dots \ n_{p}}},$ … ${\binom {n}{n_{1}\ n_{2}\ \dots \ n_{p}}},$ ${\binom {n}{n_{1}\ n_{2}\ \dots \ n_{p}}},$ ${\displaystyle {\binom {n}{n_{1}\n_{2}\dots \n_{p}},$ 즉 모든 ${\binom {n}{n_{1}\ n_{2}\ \dots \ n_{p}}},$ n이_i 가능한 한 거의 동일한 계수(즉, 최대 1개 차이)임을 증명했습니다. 메살킨은 일반화된 LYM 부등식을 증명하여 이를 증명했습니다.

경우 p = 2는 S 2 = E ∖ S 1 {\displaystyle S_{2}=E\setminus S_{1}이기 때문에 슈페르너의 정리이며, 가정은 S 1 {\displaystyle S_{1} 집합으로 축소됩니다.

집합의 p-구성에 긴 사슬이 없음

Beck & Zaslavsky(2002)는 일반화된 LYM 부등식에 대한 Meshalkin의 증명을 적용하여 Erdös 정리와 Meshalkin 정리를 결합했습니다. 그들은 중복을 무시하고 p- tup의 i번째 위치에 있는 집합이 r-체인이 없는 p- compos 제품군 중 가장 큰 크기임을 보여주었습니다. 모든 i= $i=1,2,\dots ,p-1$ 1 $i=1,2,\dots ,p-1$ 2, …, p - 1 {\display i=1, 2,\dots,p-1}에 $i=1,2,\dots ,p-1$ . $r^{p-1}$ $r^{p-1}$ - $r^{p-1}$ $r^{p-1}$ 개의 가장 큰 p-multin 계수의 합보다 크지 않습니다.

투영기하학 아날로그

유한한 차수 q 위에 차원 d의 유한 사영 기하학 PG(d, F_q)에서 L ${\mathcal {L}}(p,F_{q})$ ( ${\mathcal {L}}(p,F_{q})$ ${\mathcal {L}}(p,F_{q})$ q $)$ {\ $displaystyle$ {\ $mathcal {L}}(p, F_{q})$ 를 ${\mathcal L}(p,F_{q})$ 모든 부분 공간의 족이라고 합니다. 부분적으로 집합 포함으로 순서를 정하면 이 가군은 격자입니다. 로타 & 하퍼(1971)는 ${\mathcal {L}}(p,F_{q})$ F ${\mathcal {L}}(p,F_{q})$ ${\mathcal {L}}(p, F_{q})$ 에서 안티체인의 가장 큰 크기가 가장 큰 가우스 계수 ${\begin{bmatrix}d+1\\k\end{bmatrix}};$ + ${\begin{bmatrix}d+1\\k\end{bmatrix}};$ k ${\begin{bmatrix}d+1\\k\end{bmatrix}};$ 임을 ${\mathcal {L}}(p,F_{q})$ 증명했습니다 ${\begin{bmatrix}d+1\\k\end{bmatrix}};$ ${\displaystyle {\begin{bmatrix}d+1\k\end{bmatrix}};$ 이것은 ${\begin{bmatrix}d+1\\k\end{bmatrix}};$ 슈퍼너 정리의 투영 기하학 아날로그 또는 q-아날로그입니다.

그들은 ${\mathcal {L}}(p,F_{q})$ L ${\mathcal {L}}(p,F_{q})$ ${\mathcal {L}}(p,F_{q})$ ${\displaystyle {\mathcal {L}}(p,F_{q})$ 에서 r-체인이 없는 패밀리의 가장 큰 크기가 가장 큰 가우스 계수의 합임을 ${\mathcal {L}}(p,F_{q})$ 증명했습니다. 그들의 증거는 LYM 불평등의 투영적 유사성에 의한 것입니다.

사영 공간의 p-구성에 긴 사슬이 없음

Beck & Zaslavsky (2003)는 Rota-Harper 정리의 Meshalkin과 같은 일반화를 얻었습니다. PG(d, F_q)에서 길이 p의 메시알킨 시퀀스는 투영 부분공간의 시퀀스 $(A_{1},\ldots ,A_{p})$ 1 $(A_{1},\ldots ,A_{p})$ $(A_{1},\ldots ,A_{p})$ $(A_{1},\ldots ,A_{p})$ ${\displaystyle(A_{1},\ldots, A_{p})}$ 이며, PG(d_q, F)의 적절한 부분공간이 모두 포함하지 않고 차원의 합은 $d-p+1$ - p $d-p+1$ + $d-p+1$ $d-p+1$ 입니다 $d-p+1$ 정리는 PG(d, F)에서 길이가 p인 메쉬알킨 수열의 계열로, 수열의 위치 i에 나타나는 부분 공간들이 각 $i=1,2,\dots ,p-1,$ = $i=1,2,\dots ,p-1,$ 2 $…, p-1,$ {\displaystyle i=1, 2,\ dots, p-1, $}$ 수량 $i=1,2,\dots ,p-1,$ 중 $r^{p-1}$ 가장 큰 $r^{p-1}$ $r^{p-1}$ - 1 ${\$ r $^{p-1}$ 의 합 이하입니다.

{\begin{bmatrix}d+1\n_{1}\ n_{2}\ \dots \ n_{p}\end{bmatrix}}q^{s_{2}(n_{1},\ldots ,n_{p})},

여기서 ${\begin{bmatrix}d+1\\n_{1}\ n_{2}\ \dots \ n_{p}\end{bmatrix}}$ [ ${\begin{bmatrix}d+1\\n_{1}\ n_{2}\ \dots \ n_{p}\end{bmatrix}}$ + 1 ${\begin{bmatrix}d+1\\n_{1}\ n_{2}\ \dots \ n_{p}\end{bmatrix}}$ 1 ${\begin{bmatrix}d+1\\n_{1}\ n_{2}\ \dots \ n_{p}\end{bmatrix}}$ ${\begin{bmatrix}d+1\\n_{1}\ n_{2}\ \dots \ n_{p}\end{bmatrix}}$ … ${\begin{bmatrix}d+1\\n_{1}\ n_{2}\ \dots \ n_{p}\end{bmatrix}}$ ${\begin{bmatrix}d+1\\n_{1}\ n_{2}\ \dots \ n_{p}\end{bmatrix}}$ ] ${\displaystyle {\$ begin ${bmatrix}$ d+ $1$ \n $_{1}\n_{2}\ \dots$ \n_ ${p}\end$ {bmatrix}}}( $d+1=n_{1}+\cdots +n_{p}$ + $d+1=n_{1}+\cdots +n_{p}$ $=$ $d+1=n_{1}+\cdots +n_{p}$ n $1$ + $⋯$ + n {\displaystyle d+1 $=$ n_{1}+\cdots + n_{p $d+1=n_{1}+\cdots +n_{p}$ 는 p-Gaussian 계수를 나타냅니다.

{\begin{bmatrix}d+1\n_{1}\end{bmatrix}}{\begin{bmatrix}d+1-n_{1}\\n_{2}\end{bmatrix}}\cdots {\begin{bmatrix}d+1-(n_{1}+\cdots +n_{p-1})\\n_{p}\end{bmatrix}}

그리고.

s_{2}(n_{1},\ldots ,n_{p}):=n_{1}n_{2}+n_{1}n_{3}+n_{2}n_{3}+n_{1}n_{4}+\cdots +n_{p-1}n_{p},

숫자 $n_{1},n_{2},\dots ,n_{p}.$ , $n_{1},n_{2},\dots ,n_{p}.$ 2 $n_{1},n_{2},\dots ,n_{p}.$ $n_{1},n_{2},\dots ,n_{p}.$ $n_{1},n_{2},\dots ,n_{p}.$ $.$ {\ $displaystyle n_{1}, n_{2},\$ dots $,$ n_{p}의 두 번째 기본 대칭 함수입니다.

참고 항목

참고문헌

Anderson, Ian (1987), Combinatorics of Finite Sets, Oxford University Press.
Beck, Matthias; Zaslavsky, Thomas (2002), "A shorter, simpler, stronger proof of the Meshalkin-Hochberg-Hirsch bounds on componentwise antichains", Journal of Combinatorial Theory, Series A, 100 (1): 196–199, arXiv:math/0112068, doi:10.1006/jcta.2002.3295, MR 1932078, S2CID 8136773.
Beck, Matthias; Zaslavsky, Thomas (2003), "A Meshalkin theorem for projective geometries", Journal of Combinatorial Theory, Series A, 102 (2): 433–441, arXiv:math/0112069, doi:10.1016/S0097-3165(03)00049-9, MR 1979545, S2CID 992137.
Engel, Konrad (1997), Sperner theory, Encyclopedia of Mathematics and its Applications, vol. 65, Cambridge: Cambridge University Press, p. x+417, doi:10.1017/CBO9780511574719, ISBN 0-521-45206-6, MR 1429390.
Engel, K. (2001) [1994], "Sperner theorem", Encyclopedia of Mathematics, EMS Press
Erdős, P. (1945), "On a lemma of Littlewood and Offord" (PDF), Bulletin of the American Mathematical Society, 51 (12): 898–902, doi:10.1090/S0002-9904-1945-08454-7, MR 0014608
Lubell, D. (1966), "A short proof of Sperner's lemma", Journal of Combinatorial Theory, 1 (2): 299, doi:10.1016/S0021-9800(66)80035-2, MR 0194348.
Meshalkin, L.D. (1963), "Generalization of Sperner's theorem on the number of subsets of a finite set", Theory of Probability and Its Applications (in Russian), 8 (2): 203–204, doi:10.1137/1108023.
Rota, Gian-Carlo; Harper, L. H. (1971), "Matching theory, an introduction", Advances in Probability and Related Topics, Vol. 1, New York: Dekker, pp. 169–215, MR 0282855.
Sperner, Emanuel (1928), "Ein Satz über Untermengen einer endlichen Menge", Mathematische Zeitschrift (in German), 27 (1): 544–548, doi:10.1007/BF01171114, hdl:10338.dmlcz/127405, JFM 54.0090.06, S2CID 123451223.

외부 링크

슈페르너의 칼집 정리
폴리매스1위키 위의 스페르너 정리

Search