Liché podmnožiny s lichými průniky

Úkol: Nechť $ A$ je množina velikosti $ n$. Nechť $ B$ je systém jejích podmnožin liché velikosti takový, že průnik libovolných dvou prvků tohoto systému má lichou velikost. Dokažte, že $ \vert B\vert\le2^{\lfloor\frac{n-1}{2}\rfloor}$. Dokažte, že tento odhad nelze zlepšit.

Návod: Pro liché $ n$ lze využít výsledků příkladu 3.6 - uvažte systém tvořený doplňky množin ze systému $ B$. Pro sudé $ n$ (ale lze takto postupovat i pro liché $ n$) zvolte $ D\in B$ uvažte systém $ B'$ tvořenými symetrickými diferencemi8 množin systému $ B$ a množiny $ D$. Nyní již lze použít větu o dimenzi jádra a obrazu zobrazení, podobně jako v 3.6 příkladu, na charakterické vektory množin systému $ B'$ a množiny $ D$.


Řešení: Postupujme dle návodu v příkladu zároveň pro sudé i liché $ n$. Pracujme nad tělesem {\bb Z}$ _2$, označme $ \vec{d}$ charakteristický vektor (viz příklad 3.6) množiny $ D$ a nechť $ \vec{u}$ a $ \vec{v}$ jsou charakteristické vektory dvou libovolných (ne nutně různých) množin systému $ B$. Označme $ \cdot$ složkový součin vektorů, tj. $ \vec{a}\cdot \vec{b}=\sum_i a_ib_i$. Vektor $ \vec{u}+\vec{d}$ je charakteristickým vektorem množiny, která je symetrickou diferencí množiny $ D$ a množiny odpovídající vektoru $ \vec{u}$. Tedy vektory $ \vec{u}+\vec{d}$ jsou charakteristickými vektory množin systému $ B'$ a navíc charakteristické vektory všech množin tohoto systému jsou lze napsat v tomto tvaru. Podle zadání příkladu platí $ \vec{u}\cdot \vec{v}=1$. Tedy zejména platí: $ (\vec{u}+\vec{d})\cdot (\vec{v}+\vec{d})=
\vec{u}\cdot \vec{v}+\vec{u}\cdot \vec{d}+
\vec{d}\cdot \vec{v}+\vec{d}\cdot \vec{d}=4=0$ a $ \vec{d}\cdot
(\vec{v}+\vec{d})=\vec{d}\cdot \vec{v}+\vec{d}\cdot \vec{d}=2=0$.

Uvažme nyní matici $ C$, jejíž řádky jsou charakteristické vektory množin systému $ B'$ a charakteristický vektor množiny $ D$. Zřejmě charakteristické vektory všech množin systému $ B'$ leží v jádře zobrazení odpovídajícího matici $ C$; označme dimenzi lineárního obalu těchto vektorů $ c$. Hodnost matice $ C$ je $ c+1$, neboť vektor $ \vec{d}$ nelze vyjádřit jako lineární kombinaci9 ostatních řádků matice $ D$: ostatní řádky (a i jejich součty) mají totiž vždy sudý počet jedniček. Tuto skutečnost lze ověřit i jinak: kdyby platilo $ \vec{d}=\sum_{i}\vec{w}_i$, kde $ \vec{w}_i$ jsou některé z ostatních řádků matice $ C$, potom by nutně platilo $ 1=\vec{d}\cdot\vec{d}=\vec{d}\cdot\left(\sum_{i}
\vec{w}_i\right)=\sum\nolimits_{i} (\vec{d}\cdot\vec{w}_i)=
\sum_{i} 0=0$. To ale není možné a tedy $ \vec{d}$ je vektor lineárně nezávislý na ostatních řádcích matice $ C$ a tedy hodnost této matice je $ c+1$. Dle věty o dimenzi jádra a obrazu zobrazení musí platit: $ c+(c+1)\le\dim$Ker $ {}C+\dim\mathop{\rm Im}\nolimits
C=n$. Odtud plyne $ c\le\lfloor\frac{n-1}{2}\rfloor$, neboli $ \vert B\vert=\vert B'\vert\le2^{\lfloor\frac{n-1}{2}\rfloor}$.

Nechť $ x$ je libovolný prvek množiny $ A$ a označme $ A'=A\setminus\{x\}$. Nechť $ B''$ je maximální systém podmnožin $ A'$ sudé velikosti, jejichž průnik po dvou má sudou velikost. Dle výsledků příkladu 3.6 je velikost tohoto systému $ 2^{\lfloor\frac{n-1}{2}\rfloor}$. Nyní ke všem množinám systému $ B''$ přidejme prvek $ x$ a takto vzniklý systém množin označme $ B$. Systém $ B$ má zřejmě velikost $ 2^{\lfloor\frac{n-1}{2}\rfloor}$ a splňuje podmínky příkladu. Tedy odhad, dokázaný v minulém odstavci, nelze zlepšit.

$ \ast$DK$ \ast$