Antiketju

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 a ≤ b tai b ≤ a. 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 x ≤ y eikä y ≤ x.

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 }$.