Antiketju

Wikipedia
Loikkaa: valikkoon, hakuun

Matematiikassa, erityisesti järjestysteoriassa, antiketju on kahden osittain järjestetyn joukon välinen relaatio.

Olkoon S osittain järjestetty joukko S:n kaksi alkiota a ja b ovat vertailullisia jo ab tai ba. S:n ketju C on pareittain vertailullinen S:n osajoukko, eli kaikki C:n alkioit x ja y ovat vertailullisia. Toisaalta S:n antiketju on pareittain vertailemattoimien alkioiden muodostama S:n osajoukko. Siten A on S:n antiketju jos A on S:n osajoukko jolle jokainen kahden A:n alkion muodostama pari on vertailematon, eli kaikilla A:n alkioilla x ja y A ei ole voimassa xy eikä yx.

Dilworthin lauseen mukaan kokoa n+1 olevaa antiketjua A S:ssä ei ole jos ja vain jos S on yhdiste n täysin järjestetystä joukosta. Lauseen perusteella voidaan arvioida maksimaalisen antiketjun kokoa.

Spernerin lauseen mukaan äärellisen n-alkioisen joukon X, joka on järjestetty osajoukkorelaation suhteen, on maksimaalisen antiketjun koko enintään {n \choose \lfloor{n/2}\rfloor}.

Tämä matematiikkaan liittyvä artikkeli on tynkä. Voit auttaa Wikipediaa laajentamalla artikkelia.