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 .Konhauser, Velleman, Wagon: Which Way did the Bicycle GoE. S. Sperner, Ein Satz über Untermengen einer endlichen Menge, Mathematische Bulletin 16 (1973) 343–345D. Lubell, A short proof of Sperner's lemma, Journal of Combinatorial Theory 1 (1966) 299.

  Lähteet  

Luokka:Järjestysteoria
Luokka:Kombinatoriikka