Sudé podmnožiny se sudými průniky

Úkol: Nechť $ A$ je množina velikosti $ n$. Nechť $ B$ je systém jejích podmnožin sudé velikosti takový, že průnik libovolných dvou množin tohoto systému má sudou velikost. Dokažte, že $ \vert B\vert\le 2^{\lfloor\frac{n}{2}\rfloor}$; $ \lfloor x\rfloor$ pro $ x\in${\bb R} je nejbližší celé číslo menší nebo rovné $ x$, tedy označuje zaokrouhlování dolů. Použijte větu o dimenzi jádra a obrazu zobrazení; pracujte nad tělesem {\bb Z}$ _2$. Dokažte, že tento odhad nelze zlepšit.


Řešení: Označme $ C$ matici, která jako řádky obsahuje charakteristické vektory množin systému $ B$. Charakteristický vektor množiny $ D\subseteq A$ je vektor z prostoru {\bb Z}$ _2^n$, jehož $ i$-tá složka je jedna právě tehdy, když $ i$-tý prvek množiny $ A$ náleží množině $ D$. Pro lepší porozumění uveďme příklad: $ A=\{1,2,\ldots,6\}$,

$\displaystyle B=\left\{\begin{array}{c}\{1,2,3,4\}\\ \{2,3\}\\
\{2,3,5,6\}\en...
...ccccccccccccc} 1&1&1&1&0&0\cr 0&1&1&0&0&0\cr 0&1&1&0&1&1\end{array}\right)\,.
$

Protože všechny množiny mají sudou velikost a jejich průniky po dvou taktéž, je charakteristický vektor ($ \vec{v}$) libovolné množiny systému $ B$ prvkem jádra zobrazení odpovídajícího matici $ C$ (násobíme-li $ C\vec{v}=\vec{u}$, pak každá z komponent $ \vec{u}$ je sudé číslo, tedy nula).

Označme $ h$ hodnost matice $ C$, tj. dimenzi obrazu zobrazení odpovídajícího matici $ C$; ta je určitě menší nebo rovná počtu řádků matice $ C$. Jádro tohoto zobrazení obsahuje (práve díky podmínce na sudost průniků) všechny řádky matice $ C$ a tedy jeho dimenze je alespoň $ h$. Dle věty o dimenzi jádra a obrazu zobrazení musí platit: $ h+h\le\dim$Ker $ {}C+\dim\mathop{\rm Im}\nolimits
C=n$. Tedy platí $ h\le\lfloor\frac{n}{2}\rfloor$. Všechny charakteristické vektory množin systému $ B$ leží v lineárním obalu řádků matice $ C$, protože samy jsou řádky této matice; ten má dimenzi $ h$ a tedy obsahuje nejvýše $ 2^h$ různých vektorů (všechny $ h$-dimenzionální podprostory mají stejný počet prvků). Systém $ B$ tedy obsahuje nejvýše $ 2^h\le2^{\lfloor\frac{n}{2}\rfloor}$ množin.

Nyní sestrojíme systém množin $ B$, který má vlastnosti popsané v zadání příkladu, a jehož velikost je $ 2^{\lfloor\frac{n}{2}\rfloor}$. Sdružíme prvky množiny $ A$ do $ \lfloor\frac{n}{2}\rfloor$ dvojic; je-li $ n$ liché, jeden prvek zbude. Vytvářený systém $ B$ bude obsahovat všechny podmnožiny množiny $ A$ takové, že je lze zapsat jako sjednocení právě vytvořených dvojic. Počet prvků takto vytvořeného systému $ B$ je $ 2^{\lfloor\frac{n}{2}\rfloor}$ a zřejmě splňuje vlastnosti, které na něj klade zadání příkladu.

$ \ast$DK$ \ast$