Skip to main content
LibreTexts - Ukrayinska

1.8: Теорема Спернера

  1. Last updated
  2. Save as PDF
  • Page ID
    64402

    • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

    Біноміальні коефіцієнти підраховують підмножини заданої множини; самі множини варто подивитися. Спочатку кілька зручних позначень:

    Визначення\(\PageIndex{1}\)

    Нехай\([n]=\{1,2,3,\ldots,n\}\). Потім\(\displaystyle 2^{[n]}\) позначає множину всіх підмножин\([n]\), і\(\left[\begin{array}{c}n\\k\end{array}\right]\) позначає безліч підмножин\([n]\) розміру\(k\).

    Приклад\(\PageIndex{1}\)

    Нехай\(n=3\). Тоді\[\eqalign{ \left[\begin{array}{c}n\\0\end{array}\right]&=\{\emptyset\}\cr \left[\begin{array}{c}n\\1\end{array}\right]&=\{\{1\},\{2\},\{3\}\}\cr \left[\begin{array}{c}n\\2\end{array}\right]&=\{\{1,2\},\{1,3\},\{2,3\}\}\cr \left[\begin{array}{c}n\\3\end{array}\right]&=\{\{1,2,3\}\}\cr }\nonumber\]

    Визначення\(\PageIndex{2}\): Chain

    Ланцюжок в\(\displaystyle 2^{[n]}\) - це набір підмножин\(\displaystyle 2^{[n]}\), які лінійно впорядковані шляхом включення. Анти-ланцюг в\(\displaystyle 2^{[n]}\) - це набір підмножин\(\displaystyle 2^{[n]}\), які попарно незрівнянні.

    Приклад\(\PageIndex{2}\)

    В\(\displaystyle 2^{[3]}\),\(\displaystyle \{ \emptyset,\{1\},\{1,2,3\} \}\) є ланцюг, тому що\(\displaystyle \emptyset\subseteq \{1\}\subseteq \{1,2,3\}\). Кожен\(\left[\begin{array}{c}n\\k\end{array}\right]\) - це анти-ланцюг, як є\(\displaystyle \{ \{1\},\{2,3\} \}\). У\(\displaystyle \{ \{1\},\{1,3\},\{2,3\} \}\) комплекті немає ні ланцюга, ні антиланцюга.

    Через теорему 1.4.3 ми знаємо, що серед усіх антиланцюгів форми\(\left[\begin{array}{c}n\\k\end{array}\right]\) найбільшими є «середні», а саме\(\left[\begin{array}{c}n\\ \lfloor n/2\rfloor\end{array}\right]\) і\(\left[\begin{array}{c}n \\ \lceil n/2\rceil\end{array}\right]\) (які однакові, якщо\(n\) парні). Що примітно, це найбільші з усіх антіланцюгів, тобто строго більші за всякі інші антіланцюга. Коли\(n=3\), анти-ланцюги\(\left[\begin{array}{c}3\\1\end{array}\right]\) і\(\left[\begin{array}{c}3\\2\end{array}\right]\) є єдиними анти-ланцюгами розміру 3, і немає анти-ланцюга більше, як ви можете переконатися, вивчивши всі можливості.

    Перш ніж ми це доведемо, трохи позначення.

    Визначення\(\PageIndex{3}\): Permutation

    Якщо\(\sigma\colon A\to A\) це біекція, то\(\sigma\) називається перестановкою.

    Це використання перестановки слів відрізняється від нашого попереднього використання, але ці два тісно пов'язані між собою. Розглянемо таку функцію\(\sigma\colon [n]\to[n]\). Оскільки множина\(A\) в цьому випадку є кінцевою, ми могли б в принципі перерахувати кожне значення\(\sigma\):

    \[\sigma(1),\sigma(2),\sigma(3),\ldots,\sigma(n).\nonumber \]

    Це список чисел\(\{1,\ldots,n\}\) у певному порядку, а саме, це перестановка відповідно до нашого попереднього використання. Ми можемо продовжувати використовувати одне і те ж слово для обох ідей, спираючись на контекст або явне твердження, щоб вказати, що ми маємо на увазі.

    Теорема \(\PageIndex{1}\): Sperner's Theorem

    Єдині антиланцюги найбільшого розміру - це\(\left[\begin{array}{c}n \\ \lfloor n/2\rfloor\end{array}\right]\) і\(\left[\begin{array}{c} n \\ \lceil n/2\rceil\end{array}\right]\).

    Доказ

    Спочатку ми покажемо, що жоден анти-ланцюг не більший за ці два. Ми намагаємося\(\displaystyle 2^{[n]}\) розділити на\(k={n\choose \lfloor n/2\rfloor}\) ланцюжки, тобто знайти ланцюжки\[\eqalign{ &A_{1,0}\subseteq A_{1,1}\subseteq A_{1,2}\subseteq\cdots\subseteq A_{1,m_1}\cr &A_{2,0}\subseteq A_{2,1}\subseteq A_{2,2}\subseteq\cdots\subseteq A_{2,m_2}\cr &\vdots\cr &A_{k,0}\subseteq A_{k,1}\subseteq A_{k,2}\subseteq\cdots\subseteq A_{k,m_k}\cr }\nonumber\] так, щоб кожна підмножина\([n]\) з'являється рівно один раз як один з\(\displaystyle A_{i,j}\). Якщо нам вдасться знайти таку перегородку, то так як в одній ланцюжку не може перебувати два елементи антіланцюга, то жоден антиланцюг не може мати більше\(k\) елементів.

    Для невеликих значень\(n\) це можна зробити вручну; бо у\(n=3\) нас є\[\eqalign{ &\emptyset\subseteq\{1\}\subseteq\{1,2\}\subseteq\{1,2,3\}\cr &\{2\}\subseteq\{2,3\}\cr &\{3\}\subseteq\{1,3\}\cr }\nonumber\]

    Ці невеликі випадки складають основу індукції. Доведемо, що будь-який\(\displaystyle 2^{[n]}\) може бути розділений на такі ланцюжки з двома додатковими властивостями:

    1. Кожен набір в ланцюжку містить рівно на один елемент більше, ніж наступний найменший набір в ланцюжку.
    2. Сума розмірів найменшого і найбільшого елемента ланцюга дорівнює\(n\).

    Зверніть увагу, що ланцюжки для корпусу\(n=3\) мають обидва ці властивості. Дві властивості, взяті разом, означають, що кожен ланцюжок «перетинає середину»,\(n\) тобто кожен ланцюжок містить елемент\(\left[\begin{array}{c}n \\ n/2\end{array}\right]\) якщо парний, а елемент обох\(\left[\begin{array}{c}n \\ \lfloor n/2\rfloor\end{array}\right]\) і\(\left[\begin{array}{c}n \\ \lceil n/2\rceil\end{array}\right]\) якщо\(n\) непарний. Таким чином, якщо нам вдасться показати, що такі ланцюгові перегородки існують, будуть точно\(n\choose \lfloor n/2\rfloor\) ланцюги.

    Для індукційного кроку ми припускаємо, що ми\(\displaystyle 2^{[n-1]}\) розділили на такі ланцюги, і будуємо ланцюги для\(\displaystyle 2^{[n]}\).

    Спочатку для кожного ланцюжка\(A_{i,0}\subseteq A_{i,1}\subseteq\cdots\subseteq A_{i,m_i}\) формуємо нову ланцюжок\(A_{i,0}\subseteq A_{i,1}\subseteq\cdots\subseteq A_{i,m_i}\subseteq A_{i,m_i}\cup \{n\}\). З тих пір\(|A_{i,0}|+|A_{i,m_i}|=n-1\)\(|A_{i,0}|+|A_{i,m_i}\cup \{n\}|=n\), таким чином цей новий ланцюг задовольняє властивості (1) і (2).

    Крім того, якщо\(m_i>0\), формуємо нову ланцюжок\(A_{i,0}\cup \{n\}\subseteq A_{i,1}\cup \{n\}\subseteq\cdots\subseteq A_{i,m_i-1}\cup \{n\}\). Тепер\[\eqalign{ |A_{i,0}\cup \{n\}|+|A_{i,m_i-1}\cup \{n\}|&= |A_{i,0}|+1+|A_{i,m_i-1}|+1\cr &=|A_{i,0}|+1+|A_{i,m_i}|-1 +1\cr &=n-1+1=n\cr }\nonumber\] так знову властивості (1) і (2) задоволені.

    Через першого типу ланцюга всі підмножини\([n-1]\) містяться рівно один раз в новому наборі ланцюгів. Крім того, ми додали елемент\(n\) рівно один раз до кожного підмножини\([n-1]\), тому ми включили кожен підмножина\([n]\) містить\(n\) точно один раз. Таким чином ми виготовили потрібний розділ\(\displaystyle 2^{[n]}\).

    Тепер потрібно показати, що єдиними найбільшими антиланцюгами є\(\left[\begin{array}{c}n \\ \lfloor n/2\rfloor\end{array}\right]\) і\(\left[\begin{array}{c}n \\ \lceil n/2\rceil\end{array}\right]\).

    Припустимо, що\(A_1,A_2,…,A_m\) це анти-ланцюг; то\(A_1^c,A_2^c,…,A_m^c\) також анти-ланцюг, де\(A^c\) позначає доповнення\(A\). Таким чином, якщо є антиланцюг, який містить деякі\(A\) з\(|A|>\lceil n/2\rceil\), є також один містить\(A^c\), і\(|A^c|< \lfloor n/2\rfloor\). Припустимо, що якийсь анти-ланцюг містить набір\(A\) с\(|A|< \lfloor n/2\rfloor\). Далі ми доведемо, що цей антиланцюг не може бути максимального розміру.

    Розділ\(\displaystyle 2^{[n]}\) як у першій частині доказу. Припустимо, що\(A\) це підмножина елементів одного або двох елементних ланцюга\(C\), тобто ланцюга, що складається виключно з набору\(S_1\) розміру\(n/2\), якщо\(n\) парний, або множин\(S_1\) і\(S_2\) розмірів\(\lfloor n/2\rfloor\) і\(\lceil n/2\rceil\), з\(A\subseteq S_1\subseteq S_2\), якщо\(n\) є непарний. Тоді жоден член не\(C\) знаходиться в анти-ланцюзі. Таким чином, максимально можливий розмір для антиланцюга, що містить\(A\) є\({n\choose \lfloor n/2\rfloor}-1\).

    Якщо не\(A\) є підмножиною елементів такого короткого ланцюжка, ми тепер доведемо, що існує ще один ланцюговий розділ\(\displaystyle 2^{[n]}\), який має цю властивість. Зверніть увагу, що в оригінальній перегородці ланцюга повинна бути ланцюжок довжиною 1 або 2\(C_1\), що складається з\(S_1\) і можливо\(S_2\); якщо ні, то кожен ланцюжок містив би набір розміру\(\lfloor n/2\rfloor -1\), але таких наборів недостатньо для обходу. Припустимо, що\(A=\{x_1,\ldots,x_k\}\) і набір\(S_1\) в\(C_1\) є\(S_1=\{x_1,\ldots,x_q,y_{q+1},\ldots y_l\}\), де\(0\le q< k\) і\(l>k\).

    \(\sigma\)Дозволяти бути перестановкою\([n]\) таких, що\(\sigma(x_{q+i})=y_{q+i}\) і\(\sigma(y_{q+i})=x_{q+i}\), для\(1\le i\le k-q\), і\(\sigma\) фіксує всі інші елементи. Тепер для\(U\subseteq [n]\), нехай\(\overline U=\sigma(U)\), і зауважте, що\(U\subseteq V\) якщо і тільки якщо\(\overline U\subseteq\overline V\). Таким чином, кожен ланцюжок в оригінальній перегородці ланцюга відображає ланцюжок. Оскільки\(\sigma\) це біекція, ці нові ланцюги також утворюють\(\displaystyle 2^{[n]}\) перегородку з додатковими властивостями (1) та (2). За визначенням\(\sigma\)\(A\subseteq\overline S_1\), і\(\{\overline S_1,\overline S_2\}\) є ланцюгом, скажімо\(\overline C_1\). Таким чином, цей новий ланцюговий розділ має бажану властивість:\(A\) є підмножиною кожного елемента ланцюга 1 або 2 елементів\(\overline C_1\), тому не\(A\) знаходиться в антиланцюжку максимального розміру.

    Нарешті, нам потрібно показати, що якщо\(n\) непарний, жоден анти-ланцюжок максимального розміру не містить наборів в обох\(\left[\begin{array}{c}n \\ \lfloor n/2\rfloor\end{array}\right]\) і\(\left[\begin{array}{c}n\\ \lceil n/2\rceil\end{array}\right]\). Припустимо, є така антіланцюг, що складається з наборів\(A_{k+1},\ldots,A_l\) в\(\left[\begin{array}{c}n \\ \lceil n/2\rceil\end{array}\right]\), де\(l={n\choose \lceil n/2\rceil}\), і\(B_1,\ldots,B_k\) в\(\left[\begin{array}{c}n \\ \lfloor n/2\rfloor\end{array}\right]\). Решта наборів в\(\left[\begin{array}{c}n\\ \lceil n/2\rceil\end{array}\right]\) є\(A_1,\ldots,A_k\), а решта набори в\(\left[\begin{array}{c}n\\ \lfloor n/2\rfloor\end{array}\right]\) є\(B_{k+1},\ldots,B_l\).

    Кожен набір\(B_i\),\(1\le i\le k\), міститься в точності\(\lceil n/2\rceil\) наборів\(\left[\begin{array}{c}n \\ \lceil n/2\rceil\end{array}\right]\), і всі повинні бути серед\(A_1,\ldots,A_k\). В середньому, то, кожен\(A_i\)\(1\le i\le k\), містить\(\lceil n/2\rceil\) набори серед\(B_1,\ldots,B_k\). Але кожен набір\(A_i\)\(1\le i\le k\), містить точно\(\lceil n/2\rceil\) набори в\(\left[\begin{array}{c}n \\ \lfloor n/2\rfloor\end{array}\right]\), і тому кожен повинен містити точно\(\lceil n/2\rceil\)\(B_1,\ldots,B_k\) набори і жоден з наборів\(B_{k+1},\ldots,B_l\).

    Нехай\(A_1=A_{j_1}=\{x_1,\ldots,x_r\}\) і\(B_{k+1}=\{x_1,\ldots,x_s,y_{s+1},\ldots,y_{r-1}\}\). Нехай\(B_{i_m}=A_{j_m}\backslash\{x_{s+m}\}\) і\(A_{j_{m+1}}=B_{i_m}\cup\{y_{s+m}\}\), для\(1\le m\le r-s-1\). Зверніть увагу, що до попереднього обговорення,\(1\le i_m\le k\) і\(1\le j_m\le k\). Тоді\(A_{j_{r-s}}=\{x_1,\ldots,x_s,y_{s+1},\ldots,y_{r-1},x_r\}\), значить\(A_{j_{r-s}}\supseteq B_{k+1}\), протиріччя. Звідси немає такої антіланцюга.

    Автори та авторства