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}.[1][2][3]

Viitteet[muokkaa | muokkaa wikitekstiä]

  1. Konhauser, Velleman, Wagon: Which Way did the Bicycle Go
  2. E. S. Sperner, Ein Satz über Untermengen einer endlichen Menge, Mathematische Bulletin 16 (1973) 343–345
  3. D. Lubell, A short proof of Sperner's lemma, Journal of Combinatorial Theory 1 (1966) 299.
Tämä matematiikkaan liittyvä artikkeli on tynkä. Voit auttaa Wikipediaa laajentamalla artikkelia.