Циклический многогранник

редактировать

В математике: циклический многогранник, обозначенный C (n, d), представляет собой выпуклый многогранник, образованный как выпуклая оболочка из n различных точек на рациональной нормальной кривой в R, где n больше d. Эти многогранники изучали Константин Каратеодори, Дэвид Гейл, Теодор Моцкин, Виктор Клее и другие. Они играют важную роль в полиэдральной комбинаторике : согласно теореме о верхней границе, доказанной Питером МакМалленом и Ричардом Стэнли, граница Δ (n, d) циклического многогранника C (n, d) максимизирует число f i i-мерных граней среди всех симплициальных сфер размерности d - 1 с n вершинами.

Содержание

1 Определение
2 Условие равномерности шторма
3 Соседство
4 Количество граней
5 Теорема о верхней границе
6 См. Также
7 Ссылки

Определение

кривая момента в $R d {\ displaystyle \ mathbb {R} ^ {d}}$ $\ mathbb {R} ^ {d}$ определяется как

x: R → Р d, x (t): знак равно [t, t 2,…, td] T {\ displaystyle \ mathbf {x}: \ mathbb {R} \ rightarrow \ mathbb {R} ^ {d}, \ mathbf {x } (t): = {\ begin {bmatrix} t, t ^ {2}, \ ldots, t ^ {d} \ end {bmatrix}} ^ {T}}

{\ displaystyle \ mathbf {x}: \ mathbb {R} \ rightarrow \ mathbb { R} ^ {d}, \ mathbf {x} (t): = {\ begin {bmatrix} t, t ^ {2}, \ ldots, t ^ {d} \ end {bmatrix}} ^ {T}}

$d {\ displaystyle d}$ $d$ -мерный циклический многогранник с $n {\ displaystyle n}$ $n$ вершинами - это выпуклая оболочка

C (n, d): = conv {x (T 1), Икс (T 2),…, Икс (ТН)} {\ Displaystyle C (N, d): = \ mathbf {conv} \ {\ mathbf {x} (t_ {1}), \ mathbf {x} (t_ {2}), \ ldots, \ mathbf {x} (t_ {n}) \}}

{\ displaystyle C (n, d): = \ mathbf {conv} \ {\ mathbf {x} (t_ {1}), \ mathbf {x } (t_ {2}), \ ldots, \ mathbf {x} (t_ {n}) \}}

из $n>d ≥ 2 {\ displaystyle n>d \ geq 2}$ $n>d \ geq 2$ отдельные точки $x (ti) {\ displaystyle \ mathbf {x} (t_ {i})}$ ${\ displaystyle \ mathbf {x} (t_ {i})}$ с $t 1 < t 2 < … < t n {\displaystyle t_{1}$ $t_ {1} <t_ {2} <\ ldots <t_{n}$ на кривой момента.

Комбинаторная структура этого многогранника не зависит от выбранных точек, и результирующий многогранник имеет размерность d и n вершин. Его границей является (d - 1) -мерный симплициальный многогранник, обозначенный Δ (n, d).

Условие четности Гейла

Условие четности Гейла обеспечивает необходимое и достаточное условие для определения фасеты на циклическом многограннике.

Пусть $T: = {t 1, t 2,…, tn} {\ displaystyle T: = \ {t_ {1}, t_ {2}, \ ldots, t_ {n} \ }}$ ${\ displaystyle T: = \ { t_ {1}, t_ {2}, \ ldots, t_ {n} \}}$ . Затем a $d {\ displaystyle d}$ $d$ -subset $T d ⊆ T {\ displaystyle T_ {d} \ substeq T}$ ${\ displaystyle T_ {d} \ substeq T}$ образует фасет $C (n, d) {\ displaystyle C (n, d)}$ ${\ displaystyle C (n, d)}$ iff любые два элемента в $T ∖ T d {\ displaystyle T \ setminus T_ {d}}$ ${\ displaystyle T \ setminus T_ {d}}$ разделены четным числом элементов из $T d {\ displaystyle T_ {d}}$ $T_ {d}$ в последовательности $(t 1, t 2,…, tn) {\ displaystyle (t_ {1}, t_ {2}, \ ldots, t_ {n})}$ ${\ displaystyle (t_ {1}, t_ {2}, \ ldots, t_ {n})}$ .

Соседство

Циклические многогранники являются примерами соседних многогранников, в которых каждый набор из большинство d / 2 вершин образуют грань. Они были первыми известными соседними многогранниками, и Теодор Моцкин предположил, что все соседние многогранники комбинаторно эквивалентны циклическим многогранникам, но теперь известно, что это неверно.

Количество граней

Количество i-мерных граней циклического многогранника Δ (n, d) задается формулой

fi (Δ (n, d)) = (ni + 1) для 0 ≤ i < ⌊ d 2 ⌋ {\displaystyle f_{i}(\Delta (n,d))={\binom {n}{i+1}}\quad {\textrm {for}}\quad 0\leq i<\left\lfloor {\frac {d}{2}}\right\rfloor }

{\ displaystyle f_ {i} (\ Delta (n, d)) = {\ binom { n} {i + 1}} \ quad {\ textrm {for}} \ quad 0 \ leq i <\ left \ lfloor {\ frac {d} {2}} \ right \ rfloor}

и $(f 0,…, f ⌊ d 2 ⌋ - 1) {\ displaystyle (f_ {0}, \ ldots, f _ {\ left \ lfloor {\ frac {d} {2}} \ right \ rfloor -1})}$ ${\ displaystyle (f_ {0}, \ ldots, f _ {\ left \ lfloo r {\ frac {d} {2}} \ right \ rfloor -1})}$ полностью определить $(f ⌊ d 2 ⌋,…, fd - 1) {\ displaystyle (f _ {\ left \ lfloor {\ frac {d} {2}} \ right \ rfloor}, \ ldots, f_ {d-1})}$ ${\ displaystyle (f _ {\ left \ lfloor {\ frac { d} {2}} \ right \ rfloor}, \ ldots, f_ {d-1})}$ через уравнения Дена – Соммервилля.

Теорема о верхней границе

Теорема о верхней оценке утверждает, что циклические многогранники имеют максимально возможное количество граней для данной размерности и количества вершин: если ∆ - симплициальная сфера размерности d - 1 с n вершинами, то

fi (∆) ≤ fi (∆ (n, d)) для i = 0, 1,…, d - 1. { \ displaystyle f_ {i} (\ Delta) \ leq f_ {i} (\ Delta (n, d)) \ quad {\ textrm {for}} \ quad i = 0,1, \ ldots, d-1.}

f_ {i} (\ Delta) \ leq f_ {i} (\ Delta (n, d)) \ quad {\ textrm {for}} \ quad i = 0,1, \ ldots, d-1.

Гипотеза о верхней границе для симплициальных многогранников была предложена Теодором Моцкиным в 1957 году и доказана Питером Макмалленом в 1970 году. Виктор Клее предположил, что это же утверждение должно выполняться для всех симплициальных сфер, и это действительно было установлено в 1975 г. Ричардом П. Стэнли с использованием понятия кольца Стэнли – Рейснера и гомологических методов.

См. Также

Комбинаторная коммутативная алгебра

Ссылки