Kısmi Sıralı Kümeler
Kısmi sıralı küme veya poset, tüm çiftlerin karşılaştırılabilir olmasını gerektirmeksizin, bir elemanın diğerinden önce gelmesi veya altında olması fikrini yakalayan bir ilişkiyle birlikte bir kümedir.
Tanım
Kısmi sıralı bir küme, yansımalı (reflexive), anti-simetrik (antisymmetric) ve geçişli (transitive) olan ikili bir ilişkiye sahip bir kümedir; bu ilişki altında elemanlar karşılaştırılabilir veya karşılaştırılamaz olabilmektedir.
Kapsam
Bu konu, kısmi sıralama aksiyomlarını, Hasse diyagramlarını, zincirleri ve anti-zincirleri, maksimal ve minimal elemanları, sıra koruyan haritaları ve dualiteyi, ayrıca Dilworth ve Mirsky'nin kombinatoryal yapı teoremlerini kapsamaktadır. Ayrıca, genel dahil etme-hariç tutma (inclusion-exclusion) ilkesinin arkasındaki sıra-teorik motor olan bir poset'in Mobius fonksiyonu da tanıtılmaktadır.
Temel sorular
- Elemanlar arasındaki bir öncelik ilişkisi nasıl aksiyomatize edilir ve çizilir?
- Bir poset'in elemanları zincirlere veya anti-zincirlere nasıl ayrılır?
- Bir poset'teki en büyük anti-zincir veya en uzun zincir nedir?
- Mobius fonksiyonu, dahil etme-hariç tutma ilkesiyle saymayı nasıl genelleştirmektedir?
Anahtar kavramlar
- Kısmi sıralama aksiyomları
- Hasse diyagramı
- Zincirler ve anti-zincirler
- Maksimal ve minimal elemanlar
- Dilworth teoremi
- Mobius fonksiyonu
Temel kuramlar
- Dilworth teoremi
- Herhangi bir sonlu poset'te, tüm elemanları kapsamak için gereken minimum zincir sayısı, bir anti-zincirin maksimum boyutuna eşittir; bu, birçok kombinatoryal sonucu olan temel bir min-maks dualitesidir.
- Bir poset'in Mobius fonksiyonu
- Her yerel olarak sonlu poset, sıra üzerindeki toplamayı tersine çeviren bir Mobius fonksiyonu taşımaktadır; Rota'nın teorisi bunu, dahil etme-hariç tutma ve sayı teorik tersine çevirmenin birleştirici kaynağı haline getirmektedir.
Klinik önem
Posetler, bağımlılıkları olan görev çizelgelemesini, sürüm ve kalıtım hiyerarşilerini, tercih ve kapsama ilişkilerini modellemektedir; zincir ve anti-zincir ayrışımları ise çizelgeleme ve sıralama algoritmalarında yer almaktadır.
Tarihçe
Dilworth'ün 1950 tarihli zincir-anti-zincir teoremi ve Rota'nın 1964 tarihli Mobius fonksiyonları temelleri, sıralı kümelerin kombinatoryal çalışmasını modern ayrık matematiğin merkezi bir konusu haline dönüştürmüştür.
Öne çıkan isimler
- Robert Dilworth
- Gian-Carlo Rota
- Richard P. Stanley
İlgili konular
Temel eserler
- davey2002
- stanley2011
Sıkça sorulan sorular
- Hasse diyagramı nedir?
- Sonlu bir poset'in bir çizimidir; bu çizimde her eleman, kapsadığı elemanların üzerine yerleştirilmiş bir nokta olarak gösterilir ve sadece kapsayan çiftler arasında kenarlar bulunur, böylece sıra yukarı doğru okunmaktadır.
- Anti-zincir nedir?
- Anti-zincir, hiçbir ikisi karşılaştırılabilir olmayan bir eleman kümesidir; örneğin, hiçbiri diğerini içermeyen bir alt küme koleksiyonu gibi tanımlanabilir.