Bondysova věta - Bondys theorem - Wikipedia

V matematice Bondyho věta je vázáno na počet prvků potřebných k rozlišení množin v a rodina sad od sebe navzájem. Patří do oblasti kombinatorika, a je pojmenována po John Adrian Bondy, který jej publikoval v roce 1972.^[1]

Prohlášení

Věta je následující:

Nechat X být set s n prvky a nechat A₁, A₂, ..., A_n být odlišné podmnožiny X. Pak existuje podmnožina S z X s n - 1 prvky takové, že sady A_i ∩ S jsou všechny odlišné.

Jinými slovy, pokud máme 0-1 matice s n řádky a n sloupce, takže každý řádek je odlišný, můžeme odebrat jeden sloupec tak, aby řádky výsledného n × (n - 1) matice jsou odlišné.^[2][3]

Příklad

Zvažte matici 4 × 4

${ displaystyle { begin {bmatrix} 1 & 1 & 0 & 1 0 & 1 & 0 & 1 0 & 0 & 1 & 1 0 & 1 & 1 & 0 end {bmatrix}}}$

kde jsou všechny řádky párově odlišné. Pokud odstraníme například první sloupec, výslednou matici

${ displaystyle { begin {bmatrix} 1 & 0 & 1 1 & 0 & 1 0 & 1 & 1 1 & 1 & 0 end {bmatrix}}}$

již nemá tuto vlastnost: první řádek je totožný s druhým řádkem. Podle Bondyho věty však víme, že vždy můžeme najít sloupec, který lze odstranit, aniž bychom zavedli nějaké identické řádky. V tomto případě můžeme odstranit třetí sloupec: všechny řádky matice 3 × 4

${ displaystyle { begin {bmatrix} 1 & 1 & 1 0 & 1 & 1 0 & 0 & 1 0 & 1 & 0 end {bmatrix}}}$

jsou odlišné. Další možností by bylo smazání čtvrtého sloupce.

Aplikace teorie učení

Z pohledu teorie výpočetního učení, Bondyho věta může být přeformulována následovně:^[4]

Nechat C být koncept třídy přes konečnou doménu X. Pak existuje podmnožina S z X s velikostí maximálně |C| - 1 takový S je sada svědků pro každý koncept v C.

To znamená, že každá třída konečných konceptů C má svoje vyučovací rozměr ohraničeno |C| − 1.

Poznámky