Deficitní Hallova věta

Úloha číslo: 3763

Dokažte následující zobecnění Hallovy věty: Mějme množinový systém \((X,{\cal S})\) a přirozené číslo \(k\) takové, že sjednocení libovolného podsystému \({\cal T}\subseteq {\cal S}\) obsahuje alespoň \(\vert{\cal T}\vert-k\) prvků nosné množiny \(X\). Potom po vyřazení nejvýše \(k\) množin ze \(\cal S\) má výsledný systém množin svůj systém různých reprezentantů.

  • Řešení

    Daný problém převedeme na Hallovu větu tak, že doplníme \(X\) o \(k\) dalších prvků, které přidáme do každé množiny ze \(\mathcal S\).

    Upravený systém splňuje Hallovu podmínku, proto má systém různých reprezentantů. Po vyřazení nejvýše \(k\) množin, které jsou reprezentovány dodatečně přidanými prvky dostaneme systém reprezentantů pro redukovaný systém množin, jak bylo požadováno.

Obtížnost: Středně těžká úloha
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze