Перевернуть график

Примеры переворотов в измерении 1 (верхний правый), 2 (верхний левый и центральный ряд) и 3 (нижний ряд).

В математике флип-граф — это граф которого , вершины являются комбинаторными или геометрическими объектами, а ребра соединяют два таких объекта, когда их можно получить друг из друга с помощью элементарной операции, называемой флипом. Флип-графы — это частные случаи геометрических графов .

Среди заметных флип-графов можно найти 1-скелет многогранников, таких как ассоциэдры. ^[1] или циклоэдры . ^[2]

Примеры

Прототип флип-графа представляет собой выпуклый $n$ -гон $\pi$ . Вершины этого графа триангуляциями являются $\pi$ , и две триангуляции в нем смежны , если они отличаются одним внутренним ребром. В этом случае операция переворота заключается в замене диагоналей выпуклого четырехугольника местами. Эти диагонали представляют собой внутренние ребра, которыми различаются две соседние триангуляции в флип-графе. Полученный флип-граф одновременно является диаграммой Хассе решетки Тамари. ^[3] и 1- скелет $(n-3)$ -мерный ассоциэдр . ^[1]

Эту базовую конструкцию можно обобщить несколькими способами.

Конечные множества точек в евклидовом пространстве.

Позволять $T$ быть триангуляцией конечного набора точек ${\mathcal {A}}\subset \mathbb {R} ^{d}$ . При некоторых условиях можно преобразовать $T$ в другую триангуляцию ${\mathcal {A}}$ переворотом. Эта операция заключается в изменении способа $T$ триангулирует схему (минимально аффинно зависимое подмножество ${\mathcal {A}}$ ). Точнее, если некоторая триангуляция $\tau ^{-}$ цепи $z\subset {\mathcal {A}}$ является подмножеством $T$ , и если все клетки (грани максимальной размерности) $\tau ^{-}$ есть та же ссылка $\lambda$ в $T$ , то можно выполнить переворот внутри $T$ заменив $\lambda {\mathord {\star }}\tau ^{-}$ к $\lambda {\mathord {\star }}\tau ^{+}$ , где

X{\mathord {\star }}{Y}=\{x\cup {y}:(x,y)\in {X{\mathord {\times }}{Y}}\},

и $\tau ^{+}$ по теореме Радона является единственной другой триангуляцией $z$ . Только что изложенные условия, при которых возможен переворот, гарантируют, что эта операция приведет к триангуляции ${\mathcal {A}}$ . ^[4] Соответствующий флип-граф, вершинами которого являются триангуляции ${\mathcal {A}}$ и чьи ребра соответствуют флипам между ними, является естественным обобщением флип-графа выпуклого многоугольника, поскольку два флип-графа совпадают, когда ${\mathcal {A}}$ есть множество вершин выпуклой $n$ -гон.

Топологические поверхности

Другой вид флип-графов получается при рассмотрении триангуляции топологической поверхности : ^[5] рассмотрим такую поверхность ${\mathcal {S}}$ , поместите конечное число $n$ точек на нем и соедините их дугами так, чтобы любые две дуги никогда не пересекались. Когда этот набор дуг максимален, он разлагается ${\mathcal {S}}$ в треугольники. Если, кроме того, нет кратных дуг (отдельных дуг с одной и той же парой вершин) или петель , этот набор дуг триангуляцию определяет ${\mathcal {S}}$ .

В этой ситуации две триангуляции ${\mathcal {S}}$ которые можно получить друг из друга непрерывным преобразованием, тождественны.

Две триангуляции связаны переворотом, если они отличаются ровно на одну из дуг, из которых они состоят. Обратите внимание, что эти две триангуляции обязательно имеют одинаковое количество вершин. Как и в евклидовом случае, флип-граф ${\mathcal {S}}$ граф, вершины которого являются триангуляциями ${\mathcal {S}}$ с $n$ вершины и чьи ребра соответствуют переворотам между ними. Это определение может быть непосредственно распространено на топологические поверхности с границами .

Флип-граф поверхности обобщает флип-граф поверхности. $n$ -gon, поскольку они совпадают, когда поверхность представляет собой топологический диск с $n$ точки, расположенные на его границе.

Другие флип-графы

Ряд других флип-графов можно определить, используя альтернативные определения триангуляции. Например, флип-граф, вершины которого представляют собой центрально-симметричные триангуляции $(2d+2)$ -угольник, ребра которого соответствуют операции выполнения двух центрально-симметричных флипов, является 1- скелетом $d$ -мерный циклоэдр . ^[2] Можно также рассмотреть альтернативный флип-граф топологической поверхности, определенный путем разрешения нескольких дуг и петель в триангуляциях этой поверхности.

Флип-графы также могут быть определены с использованием комбинаторных объектов, отличных от триангуляции. Примером таких комбинаторных объектов являются мозаики домино заданной области на плоскости. В этом случае можно выполнить переворот, когда два соседних домино покрывают квадрат: он заключается в повороте этих домино на 90 градусов вокруг центра квадрата, в результате чего получается разное замощение домино одной и той же области.

Характеристики

Политопальность

Помимо ассоциэдров и циклоэдров , ряд многогранников обладают тем свойством, что их 1-скелет представляет собой перевернутый граф. Например, если ${\mathcal {A}}$ представляет собой конечное множество точек в $\mathbb {R} ^{d}$ , регулярные триангуляции ${\mathcal {A}}$ те, которые можно получить, проецируя некоторые грани $(d+1)$ -мерный многогранник на $\mathbb {R} ^{d}$ . Подграф, индуцированный этими триангуляциями в флип-графе ${\mathcal {A}}$ является -скелетом многогранника 1 , вторичным многогранником многогранника ${\mathcal {A}}$ . ^[6]

Связность

По этому свойству многогранные флип-графы являются связными . Как показал Клаус Вагнер в 1930-х годах, флип-граф топологической сферы связен. ^[7] Среди связных флип-графов можно найти также флип-графы любого конечного двумерного набора точек. ^[8] В многомерных евклидовых пространствах ситуация гораздо сложнее. Конечные множества точек $\mathbb {R} ^{d}$ с несвязными флип-графами были обнаружены всякий раз, когда $d$ это минимум 5. ^[4]^[9]^[10]

Флип-граф множества вершин 4-мерного гиперкуба , как известно, связен. ^[11] Однако пока неизвестно, всегда ли связны флип-графы конечных 3- и 4-мерных множеств точек. ^[4]

Диаметр

Максимальное количество флипов, необходимое для преобразования одной триангуляции в другую, равно диаметру флип-графа. Диаметр флип-графа выпуклой $n$ -gon был получен Дэниелом Слиатором, Робертом Тарджаном и Уильямом Терстоном. ^[12] когда $n$ является достаточно большим и Лайонелем Пурненом для всех $n$ . Этот диаметр равен $2n-10$ когда $n\geq 13$ . ^[13]

Изучен диаметр других флип-графов. Например, Клаус Вагнер предоставил квадратичную верхнюю границу диаметра флип-графа набора $n$ неотмеченные точки на сфере. ^[7] Текущая верхняя граница диаметра составляет $5.2n-33.6$ , ^[14] в то время как самая известная нижняя граница равна $7n/3+\Theta (1)$ . ^[15] Диаметр флип-графов произвольных топологических поверхностей с краем также изучен и в ряде случаев точно известен. ^[16]^[17]^[18]

См. также

Ссылки

^ Jump up to: ^а ^б Ли, Карл (1989), «Ассоциэдр и триангуляции $n$ -gon», European Journal of Combinatorics , 10 (6): 551–560, doi : 10.1016/S0195-6698(89)80072-1 , MR 1022776
^ Jump up to: ^а ^б Симион, Родика (2003), «Ассоциэдр типа B», Успехи в прикладной математике , 30 (1–2): 2–25, doi : 10.1016/S0196-8858(02)00522-5 , MR 1979780
^ Тамари, Дов (1962), «Алгебра скобок и их перечисление», Новый архив математики , серия 3, 10 : 131–146, MR 0146227
^ Jump up to: ^а ^б ^с Де Лоэра, Хесус А .; Рамбау, Йорг; Сантос, Франциско (2010). Триангуляции, структуры для алгоритмов и приложений . Алгоритмы и вычисления в математике. Том. 25. Спрингер.
^ Негами, Сейя (1994), «Диагональные перевороты в триангуляциях поверхностей», Discrete Mathematics , 135 (1–3): 225–232, doi : 10.1016/0012-365X(93)E0101-9 , MR 1310882
^ Гельфанд, Израиль М. ; Зелевинский Андрей Владимирович ; Капранов, Михаил Михайлович (1990), "Многогранники Ньютона главных A-определителей", Советская математика - Доклады , 40 : 278–281, MR 1020882
^ Jump up to: ^а ^б Вагнер, Клаус (1936), «Замечания о проблеме четырех цветов», Годовой отчет Ассоциации немецких математиков , 46 : 26–32.
^ Лоусон, Чарльз Л. (1972), «Преобразование триангуляции», Дискретная математика , 3 : 365–372, doi : 10.1016/0012-365X(72)90093-3 , MR 0311491
^ Сантос, Франциско (2000), «Множество точек, пространство триангуляции которого несвязно», Журнал Американского математического общества , 13 : 611–637, doi : 10.1090/S0894-0347-00-00330-1 , hdl : 10902/ 2584 , МР 1758756
^ Сантос, Франциско (2005), «Несвязные торические схемы Гильберта», Mathematische Annalen , 332 : 645–665, arXiv : math/0204044 , doi : 10.1007/s00208-005-0643-5 , MR 2181765
^ Пурнен, Лайонел (2013), «Флип-граф четырехмерного куба связен», Discrete & Computational Geometry , 49 : 511–530, arXiv : 1201.6543 , doi : 10.1007/s00454-013-9488-y , MR 3038527
^ Слитор, Дэниел Д.; Тарьян, Роберт Э .; Терстон, Уильям П. (1988). «Расстояние вращения, триангуляции и гиперболическая геометрия» . Журнал Американского математического общества . 1 (3): 647–681. дои : 10.1090/s0894-0347-1988-0928904-4 .
^ Пурнен, Лайонел (2014). «Диаметр ассоциэдров» . Достижения в математике . 259 : 13–42. arXiv : 1207.6296 . дои : 10.1016/j.aim.2014.02.035 . МР 3197650 .
^ Бозе, Просенджит; Вердоншот, Сандер (2012). «История флипов в комбинаторных триангуляциях». Конспекты лекций по информатике . Берлин, Гейдельберг: Springer Berlin Heidelberg. п. 29–44. дои : 10.1007/978-3-642-34191-5_3 . ISBN 978-3-642-34190-8 . ISSN 0302-9743 .
^ Фрати, Фабрицио (2017). «Нижняя граница диаметра флип-графа» . Электронный журнал комбинаторики . 24 (1): P1.43. arXiv : 1508.03473 . дои : 10.37236/5489 .
^ Парлье, Хьюго; Пурнен, Лайонел (2017). «Пространства модулей флип-графов заполняющих поверхностей» . Журнал Европейского математического общества . 19 (9): 2697–2737. arXiv : 1407.1516 . дои : 10.4171/JEMS/726 .
^ Парлье, Хьюго; Пурнен, Лайонел (2018). «Модульные флип-графы однодырочных поверхностей» . Европейский журнал комбинаторики . 67 : 158–173. arXiv : 1510.07664 . дои : 10.1016/j.ejc.2017.07.003 .
^ Парлье, Хьюго; Пурнен, Лайонел (2018). «Однажды проколотые диски, невыпуклые многоугольники и острогранники». Анналы комбинаторики . 22 (3): 619–640. arXiv : 1602.04576 . дои : 10.1007/s00026-018-0393-1 .

[CL-1] Jump up to: ^а ^б Ли, Карл (1989), «Ассоциэдр и триангуляции $n$ -gon», European Journal of Combinatorics , 10 (6): 551–560, doi : 10.1016/S0195-6698(89)80072-1 , MR 1022776

[RS-2] Jump up to: ^а ^б Симион, Родика (2003), «Ассоциэдр типа B», Успехи в прикладной математике , 30 (1–2): 2–25, doi : 10.1016/S0196-8858(02)00522-5 , MR 1979780

[3] Тамари, Дов (1962), «Алгебра скобок и их перечисление», Новый архив математики , серия 3, 10 : 131–146, MR 0146227

[DRS-4] Jump up to: ^а ^б ^с Де Лоэра, Хесус А .; Рамбау, Йорг; Сантос, Франциско (2010). Триангуляции, структуры для алгоритмов и приложений . Алгоритмы и вычисления в математике. Том. 25. Спрингер.

[5] Негами, Сейя (1994), «Диагональные перевороты в триангуляциях поверхностей», Discrete Mathematics , 135 (1–3): 225–232, doi : 10.1016/0012-365X(93)E0101-9 , MR 1310882

[GZK-6] Гельфанд, Израиль М. ; Зелевинский Андрей Владимирович ; Капранов, Михаил Михайлович (1990), "Многогранники Ньютона главных A-определителей", Советская математика - Доклады , 40 : 278–281, MR 1020882

[Wagner1936-7] Jump up to: ^а ^б Вагнер, Клаус (1936), «Замечания о проблеме четырех цветов», Годовой отчет Ассоциации немецких математиков , 46 : 26–32.

[8] Лоусон, Чарльз Л. (1972), «Преобразование триангуляции», Дискретная математика , 3 : 365–372, doi : 10.1016/0012-365X(72)90093-3 , MR 0311491

[9] Сантос, Франциско (2000), «Множество точек, пространство триангуляции которого несвязно», Журнал Американского математического общества , 13 : 611–637, doi : 10.1090/S0894-0347-00-00330-1 , hdl : 10902/ 2584 , МР 1758756

[10] Сантос, Франциско (2005), «Несвязные торические схемы Гильберта», Mathematische Annalen , 332 : 645–665, arXiv : math/0204044 , doi : 10.1007/s00208-005-0643-5 , MR 2181765

[11] Пурнен, Лайонел (2013), «Флип-граф четырехмерного куба связен», Discrete & Computational Geometry , 49 : 511–530, arXiv : 1201.6543 , doi : 10.1007/s00454-013-9488-y , MR 3038527

[12] Слитор, Дэниел Д.; Тарьян, Роберт Э .; Терстон, Уильям П. (1988). «Расстояние вращения, триангуляции и гиперболическая геометрия» . Журнал Американского математического общества . 1 (3): 647–681. дои : 10.1090/s0894-0347-1988-0928904-4 .

[13] Пурнен, Лайонел (2014). «Диаметр ассоциэдров» . Достижения в математике . 259 : 13–42. arXiv : 1207.6296 . дои : 10.1016/j.aim.2014.02.035 . МР 3197650 .

[14] Бозе, Просенджит; Вердоншот, Сандер (2012). «История флипов в комбинаторных триангуляциях». Конспекты лекций по информатике . Берлин, Гейдельберг: Springer Berlin Heidelberg. п. 29–44. дои : 10.1007/978-3-642-34191-5_3 . ISBN 978-3-642-34190-8 . ISSN 0302-9743 .

[15] Фрати, Фабрицио (2017). «Нижняя граница диаметра флип-графа» . Электронный журнал комбинаторики . 24 (1): P1.43. arXiv : 1508.03473 . дои : 10.37236/5489 .

[16] Парлье, Хьюго; Пурнен, Лайонел (2017). «Пространства модулей флип-графов заполняющих поверхностей» . Журнал Европейского математического общества . 19 (9): 2697–2737. arXiv : 1407.1516 . дои : 10.4171/JEMS/726 .

[17] Парлье, Хьюго; Пурнен, Лайонел (2018). «Модульные флип-графы однодырочных поверхностей» . Европейский журнал комбинаторики . 67 : 158–173. arXiv : 1510.07664 . дои : 10.1016/j.ejc.2017.07.003 .

[18] Парлье, Хьюго; Пурнен, Лайонел (2018). «Однажды проколотые диски, невыпуклые многоугольники и острогранники». Анналы комбинаторики . 22 (3): 619–640. arXiv : 1602.04576 . дои : 10.1007/s00026-018-0393-1 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]