В математике ассоциэдр K n — это ( n – 2) -мерный выпуклый многогранник , в котором каждая вершина соответствует способу правильной вставки открывающих и закрывающих скобок в строку из n букв, а ребра соответствуют одному применению правила ассоциативности . Эквивалентно, вершины ассоциаэдра соответствуют триангуляциям правильного многоугольника с n + 1 сторонами , а ребра соответствуют переворотам ребер, в которых одна диагональ удаляется из триангуляции и заменяется другой диагональю. Ассоциэдр также называется многогранниками Сташеффа в честь работы Джима Сташеффа , который заново открыл их в начале 1960-х годов [1] после более ранней работы над ними Дова Тамари . [2]
Одномерный ассоциаэдр K 3 представляет собой две скобки (( xy ) z ) и ( x ( yz )) трех символов, или две триангуляции квадрата. Он сам по себе является отрезком прямой.
Двумерный ассоциаэдр K 4 представляет собой пять скобок четырех символов, или пять триангуляций правильного пятиугольника. Он сам является пятиугольником и связан с диаграммой пятиугольника моноидальной категории .
Трехмерный ассоциаэдр K 5 представляет собой девятигранник с девятью гранями (три непересекающихся четырехугольника и шесть пятиугольников) и четырнадцатью вершинами, а его двойственным является триаугментированная треугольная призма .
Первоначально Джим Сташефф рассматривал эти объекты как криволинейные многогранники. Впоследствии им были даны координаты как выпуклым многогранникам несколькими различными способами; см. введение Ceballos, Santos & Ziegler (2015) для обзора. [3]
Один из методов реализации ассоциаэдра — как вторичного многогранника правильного многоугольника. [3] В этой конструкции каждая триангуляция правильного многоугольника с n + 1 сторонами соответствует точке в ( n + 1)-мерном евклидовом пространстве , i -я координата которой является общей площадью треугольников, инцидентных i- й вершине многоугольника. Например, две триангуляции единичного квадрата дают таким образом две четырехмерные точки с координатами (1, 1/2, 1, 1/2) и (1/2, 1, 1/2, 1). Выпуклая оболочка этих двух точек является реализацией ассоциаэдра K 3 . Хотя он живет в 4-мерном пространстве, он образует отрезок линии (1-мерный многогранник) внутри этого пространства. Аналогично, ассоциаэдр K 4 может быть реализован таким образом как правильный пятиугольник в пятимерном евклидовом пространстве, координаты вершин которого являются циклическими перестановками вектора (1, 2 + φ, 1, 1 + φ, 1 + φ), где φ обозначает золотое сечение . Поскольку возможные треугольники внутри правильного шестиугольника имеют площади, кратные друг другу, эта конструкция может быть использована для задания целочисленных координат (в шести измерениях) трехмерному ассоциаэдру K 5 ; однако (как уже показывает пример K 4 ) эта конструкция в общем случае приводит к иррациональным числам в качестве координат.
Другая реализация, принадлежащая Жану-Луи Лодею , основана на соответствии вершин ассоциаэдра с n- листными корневыми бинарными деревьями и напрямую производит целочисленные координаты в ( n − 2)-мерном пространстве. i -я координата реализации Лодея равна a i b i , где a i — число листовых потомков левого потомка i- го внутреннего узла дерева (в порядке слева направо), а b i — число листовых потомков правого потомка. [4]
Ассоциаэдр можно реализовать непосредственно в ( n − 2)-мерном пространстве как многогранник, у которого все векторы нормалей граней имеют координаты 0, +1 или −1. Существует экспоненциально много комбинаторно различных способов сделать это. [3] [5]
Поскольку K 5 является многогранником только с вершинами, в которых сходятся 3 ребра, возможно существование углеводорода (подобного платоновым углеводородам ), химическая структура которого представлена скелетом K 5 . [6] Этот «ассоциаэдр» C 14 H 14 будет иметь обозначение SMILES : C12-C3-C4-C1-C5-C6-C2-C7-C3-C8-C4-C5-C6-C78. Его ребра будут иметь приблизительно одинаковую длину, но вершины каждой грани не обязательно будут копланарными.
Действительно, K 5 — это почти что мисс Джонсоновское тело : кажется, что его можно сделать из квадратов и правильных пятиугольников, но это не так. Либо вершины не будут полностью копланарными, либо грани придется немного исказить, отойдя от правильности.
Число ( n − k )-мерных граней ассоциаэдра порядка n (K n +1 ) задается числовым треугольником [7] ( n , k ), показанным справа.
Число вершин в K n +1 равно n -му числу Каталана (правая диагональ в треугольнике).
Число граней в K n +1 (для n ≥2) равно n -му треугольному числу минус один (второй столбец в треугольнике), поскольку каждая грань соответствует 2- подмножеству из n объектов, группировки которых образуют решетку Тамари T n , за исключением 2-подмножества, содержащего первый и последний элементы.
Число граней всех измерений (включая сам ассоциаэдр как грань, но не включая пустое множество) является числом Шредера–Гиппарха (суммой строк треугольника). [8]
В конце 1980-х годов в связи с проблемой расстояния вращения Дэниел Слейтор , Роберт Тарьян и Уильям Терстон предоставили доказательство того, что диаметр n -мерного ассоциаэдра K n + 2 не превышает 2 n − 4 для бесконечного числа n и для всех «достаточно больших» значений n . [9] Они также доказали, что эта верхняя граница точна, когда n достаточно велико, и предположили, что «достаточно большое» означает «строго больше 9». Эта гипотеза была доказана в 2012 году Лайонелом Пурнином. [10]
В 2017 году Мизера [11] и Аркани-Хамед и др. [12] показали, что ассоциаэдр играет центральную роль в теории амплитуд рассеяния для бисопряженной кубической скалярной теории. В частности, существует ассоциаэдр в пространстве кинематики рассеяния, а амплитуда рассеяния на уровне дерева является объемом дуального ассоциаэдра. [12] Ассоциаэдр также помогает объяснить соотношения между амплитудами рассеяния открытых и закрытых струн в теории струн . [11]