Соседний многогранник - Neighborly polytope

В геометрия и многогранная комбинаторика, а k-соседский многогранник это выпуклый многогранник в котором каждый набор k или меньшее количество вершин образуют грань. Например, 2-соседний многогранник - это многогранник, в котором каждая пара вершины связан край, образуя полный график. 2-соседние многогранники с более чем четырьмя вершинами могут существовать только в пространствах четырех или более измерений, и в общем случае k-соседний многогранник (кроме симплекса) требует размерности 2k или больше. А d-суплекс является d-соседски. Многогранник называется соседним без указания k, если это k-соседский для ${\displaystyle k=\lfloor d/2\rfloor }$. Если исключить симплексы, это максимально возможное k: фактически, каждый многогранник k-соседский для некоторых ${\displaystyle k\geq 1+\lfloor d/2\rfloor }$ это симплекс.^[1]

В k-соседний многогранник с k ≥ 3 каждая двумерная грань должна быть треугольником, а в k-соседний многогранник с k ≥ 4, каждая 3-грань должна быть тетраэдром. В общем, в любом k-соседний многогранник, все грани размерности меньше k находятся симплексы.

В циклические многогранники образованные как выпуклые оболочки конечных множеств точек на кривая момента (т, т², ..., т^d) в d-мерное пространство автоматически соседствует. Теодор Моцкин предположил, что все соседние многогранники комбинаторно эквивалентны циклическим многогранникам.^[2] Однако, вопреки этой гипотезе, существует много соседних многогранников, которые не являются циклическими: количество комбинаторно различных соседних многогранников сверхэкспоненциально растет как по числу вершин многогранника, так и по размерности.^[3]

В выпуклый корпус набора случайных точек, взятых из Гауссово распределение с количеством точек, пропорциональным размерности, с большой вероятностью k-соседний по стоимости k это также пропорционально размеру.^[4]

Количество граней всех измерений соседнего многогранника в четном числе измерений определяется исключительно из его размерности и количества вершин по Уравнения Дена – Соммервилля: количество k-мерные грани, ж_k, удовлетворяет неравенству

${\displaystyle f_{k-1}\leq \sum _{i=0}^{d/2}{}^{*}\left({\binom {d-i}{k-i}}+{\binom {i}{k-d+i}}\right){\binom {n-d-1+i}{i}},}$

где звездочка означает, что суммы заканчиваются на ${\displaystyle i=\lfloor d/2\rfloor }$ и окончательный срок суммы должен быть уменьшен вдвое, если d даже.^[5] Согласно теорема о верхней оценке из Макмаллен (1970),^[6] соседние многогранники достигают максимально возможного числа граней любого п-вертекс d-мерный выпуклый многогранник.

Обобщенная версия проблема счастливого конца применяется к многомерным точечным наборам и подразумевает, что для каждого измерения d и каждый п > d существует номер м(d,п) со свойством, что каждый м указывает в общая позиция в d-мерное пространство содержит подмножество п точки, образующие вершины соседнего многогранника.^[7]

Рекомендации

1. Грюнбаум, Бранко (2003), Kaibel, Volker; Клее, Виктор; Циглер, Гюнтер М. (ред.), Выпуклые многогранники, Тексты для выпускников по математике, 221 (2-е изд.), Springer-Verlag, п. 123, ISBN  0-387-00424-6.
2. Гейл, Дэвид (1963), «Соседние и циклические многогранники», в Клее, Виктор (ред.), Выпуклость, Сиэтл, 1961 год., Симпозиумы по чистой математике, 7, Американское математическое общество, стр. 225–233, ISBN  978-0-8218-1407-9.
3. Шемер, Идо (1982), "Соседние многогранники" (PDF), Израильский математический журнал, 43 (4): 291–314, Дои:10.1007 / BF02761235.
4. Донохо, Дэвид Л.; Таннер, Джаред (2005), «Соседство случайно спроектированных симплексов в больших измерениях», Труды Национальной академии наук Соединенных Штатов Америки, 102 (27): 9452–9457, Дои:10.1073 / pnas.0502258102, ЧВК  1172250, PMID  15972808.
5. Циглер, Гюнтер М. (1995), Лекции по многогранникам, Тексты для выпускников по математике, 152, Springer-Verlag, стр. 254–258, ISBN  0-387-94365-X.
6. Макмаллен, Питер (1970), "Максимальное количество граней выпуклого многогранника", Математика, 17: 179–184, Дои:10.1112 / S0025579300002850.
7. Грюнбаум, Бранко (2003), Kaibel, Volker; Клее, Виктор; Циглер, Гюнтер М. (ред.), Выпуклые многогранники, Тексты для выпускников по математике, 221 (2-е изд.), Springer-Verlag, п. 126, ISBN  0-387-00424-6. Грюнбаум приписывает ключевую лемму этого результата, что каждый набор d + 3 точки содержат вершины a (d + 2) -вершинный циклический многогранник Мике Перлес.