Свойство Шпернера

Материал из WikiGrapp
Версия от 13:27, 1 сентября 2011; KEV (обсуждение | вклад)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Свойство Шпернера (Sperner property) — свойство конечного ранжируемого частично упорядоченного множества, состоящее в том, что мощность наибольшего независимого множества равна наибольшей мощности уровня [math]\displaystyle{ \max \{w_{i} \, | \, i \geq 0\} }[/math], где [math]\displaystyle{ \,w_{i} = |W_{i}| }[/math] и [math]\displaystyle{ \,W_{i} }[/math] — все точки [math]\displaystyle{ \,x }[/math] ранга [math]\displaystyle{ \,r(x) = i }[/math].

Литература

  • Welsh D.J.A. Matroid Theory. — New York: Academic Press, 1976.