The Postal Owl

1.   
    a) Uvažme prvočíselnou $J = \{23, 29 \} \subset I$.   
    Pak $\bigcup_{j \in J} M_j = \{1,23,29\} \cap X = \{1\}$.  
    Tedy $|\{ 23, 29 \}| = |J| = 2 > 1 = |\bigcup_{j \in J} M_j| = |\{1\}|$.   
    Systém nesplňuje Hallovu podmínku a tedy nemá systém různých reprezentantů.

    b) Systém různých reprezentantů existuje, je to například tento:

    | i  | reprezentant |
    | :-:| :-:|
    | 20 | 4  | 
    | 21 | 3  | 
    | 22 | 11 |
    |  - |  - | 
    | 24 | 6  |
    | 25 | 5  | 
    | 26 | 2  |
    | 27 | 9  |
    | 28 | 7  |
    | 29 | 1  |
    | 30 | 10 |
    |  - | -  | 
    | 32 | 8  |

2. Hallova věta: m má SRR $\iff \forall J \subseteq I: |J| \leq |\bigcup_{j \in J} M_j$

Převedeme si množinový systém na bipartitní graf s partitami X a I jako na přednášce.




* $\implies$  
    Množinový systém má $SRR \implies$  
    $\forall J \subseteq I: \exists$ párování velikosti $|J| \implies$  
    Minimální vrcholové pokrytí má velikost $|J|$.
    Neexistuje menší vrcholové pokrytí.  
    Tvrzení: Sjednocení $\bigcup_{i \in I} M_i$ má velikost alespoň $|J|$.  
        Důkaz: Kdyby mělo menší velikost, nalezli bychom menší vrcholové pokrytí, stačilo by vybrat všechny vrcholy sjednocení a protože se jedná o bipartitní graf, vybráním všech těchto vrcholů bychom pokryli i všechny hrany. Protože ale velikost minimálního pokrytí je daná, toto nelze najít.

   Toto tvrzení odpovídá pravé straně Hallovy podmínky, tedy $\square$
    
* Lemma A:

   Pro každé $j \in J$, alespoň jedna hrana vede do sjednocení, jinak by množina byla prázdná a pro $J^\prime = \{ j \}$ by $1 = |J^\prime| > |\bigcup_{j \in J^\prime} M_j| = |M_j| = 0$ $\square$

* $\impliedby$

   $\forall J \subseteq I: |J| \leq |\bigcup_{j \in J} M_j| \implies$ Minimální vrcholové pokrytí má velikost alespoň J (právě J, protože stačí vybrat J, ale to neřešíme)

  Dk: Sporem: Uvažme menší vrcholové pokrytí G, $|G| < |J|$. Pak uvažme množinu $B = G \cap \bigcup_{i\in I} M_i$. Tento průnik je určitě neprázdný, protože jinak bychom v pokrytí vybrali pouze vrcholy z $J$, alespoň jeden vrchol z J by zůstal nepokryt. A hrana vedoucí z něj (dle lemmatu A existuje) by byla také nepokryta.

  Dále se podívejme na $J^\prime = J \setminus G$. Všechny hrany z $l \in J^\prime$ musí vést do $B$, jinak by nebyly pokryty vrcholovým pokrytím (nebyly by pokryty ani v partitě sjednocení, ani v partitě J).

   Ale z podmínky platí $|B| \geq |J^\prime|$

   No ale v tom případě $|G| = |B| + |J \cap G| \geq |J^\prime| + |J \cap G| = |J|$. (Poslední rovnost dostaneme z toho, že $J \cap G$ a $J^\prime = J \setminus G$ jsou disjunktní)

   Tedy $|G| \geq |J|$, to je spor s tím, že máme menší minimální pokrytí než $|J|$


   Tak tedy máme z podmínky zaručeno, že $\forall J \subseteq I$ minimální pokrytí má velikost $|J|$, takže pro $I$ má minimální pokrytí velikost $|I|$, to odpovídá (maximálnímu) párování o velikosti $|I|$ a to už triviálně dává SRR.

Menší feedback: v pdfkách s úkoly je špatný odkaz na stránku cvičení (například v tomto pdf), nefunguje ani kliknutí ani kopírování. Je tam jiná tilda. V pdfkách ze cvičení to funguje. Osobně bych ocenil, kdyby byl odkaz přístupný někde v sově, bez nutnosti něco stahovat, ale to je jen moje lenost.