Kritický pár (teorie objednávek) - Critical pair (order theory)

Hasseův diagram dílčího řádu s kritickým párem ⟨b,C⟩. Přidání Šedá linka by udělala b<C bez nutnosti jakýchkoli dalších změn. Naopak, ⟨C,b⟩ Není kritický pár, protože d<C, ale ne d<b.

v teorie objednávek, obor v matematice, a kritický pár je dvojice prvků v a částečně objednaná sada to jsou nesrovnatelný ale to by mohlo být srovnatelné, aniž by byly vyžadovány další změny částečného pořadí.

Formálně, pojďme P = (S, ≤) být částečně objednanou sadou. Kritickým párem je pak objednaný pár (X, y) prvků S s následujícími třemi vlastnostmi:

• X a y jsou neporovnatelné v P,
• pro každého z v S, pokud z < X pak z < y, a
• pro každého z v S, pokud y < z pak X < z.

Li (X, y) je kritický pár, pak binární vztah získaný z P přidáním jediného vztahu X ≤ y je také částečná objednávka. Vlastnosti požadované od kritických párů zajišťují, že při vztahu X ≤ y je přidán, přidání nezpůsobuje žádná porušení přechodná vlastnost.

Sada R z lineární rozšíření z P říká se zvrátit kritický pár (X, y) v P pokud existuje lineární rozšíření v R pro který y nastane dříve nežX. Tuto vlastnost lze použít k charakterizaci realizátoři konečných dílčích objednávek: neprázdná množina R lineárních rozšíření je realizátor právě tehdy, když obrací každý kritický pár.

Reference

• Trotter, W. T. (1992), Kombinatorika a částečně uspořádané množiny: Dimenzionální teorie, Johns Hopkins Series in Mathematical Sciences, Baltimore: Johns Hopkins Univ. lis.