Комплекс шахматной доски
Математический объект в топологической теории графов

Комплекс шахматной доски — это особый вид абстрактного симплициального комплекса , который имеет различные приложения в топологической теории графов и алгебраической топологии . [1] [2] Неформально, комплекс ( m , n )-шахматной доски содержит все наборы позиций на шахматной доске размером m на n , где ладьи могут быть размещены без нападения друг на друга. Эквивалентно, это комплекс соответствия ( m , n ) -полного двудольного графа или комплекс независимости графа ладей размером m на n .

Определения

Для любых двух положительных целых чисел m и n комплекс ( m, n )-шахматной доски является абстрактным симплициальным комплексом с множеством вершин , содержащим все подмножества S такие, что если и являются двумя различными элементами S , то и то и другое . Множество вершин можно рассматривать как двумерную сетку («шахматную доску»), а комплекс содержит все подмножества S , которые не содержат двух клеток в одной строке или в одном столбце. Другими словами, все подмножества S такие, что ладьи могут быть размещены на них, не захватывая друг друга. Δ м , н {\displaystyle \Дельта _{м,н}} [ м ] × [ н ] {\displaystyle [м]\times [н]} ( я 1 , дж 1 ) {\displaystyle (i_{1},j_{1})} ( я 2 , дж 2 ) {\displaystyle (i_{2},j_{2})} я 1 ≠ я 2 {\displaystyle i_{1}\neq i_{2}} дж 1 ≠ дж 2 {\displaystyle j_{1}\neq j_{2}}

Комплекс шахматной доски также может быть определен кратко с помощью удаленного соединения . Пусть D m будет множеством из m дискретных точек. Тогда комплекс шахматной доски является n -кратным 2- удаленным соединением D m , обозначаемым как . [3] : 176  ( Д м ) Δ ( 2 ) ∗ н {\displaystyle (D_{m})_{\Delta (2)}^{*n}}

Другое определение — это множество всех паросочетаний в полном двудольном графе . [1] K m , n {\displaystyle K_{m,n}}

Примеры

В любом ( m , n )-комплексе шахматной доски окрестности каждой вершины имеют структуру ( m − 1, n − 1)-комплекса шахматной доски. В терминах шахматных ладей размещение одной ладьи на доске устраняет оставшиеся клетки в той же строке и столбце, оставляя меньший набор строк и столбцов, где могут быть размещены дополнительные ладьи. Это позволяет изучать топологическую структуру шахматной доски иерархически, основываясь на ее структурах меньшей размерности. Примером этого является комплекс (4,5)-шахматной доски и комплексы (3,4)- и (2,3)-шахматной доски внутри него: [4]

  • Комплекс (2,3)-шахматной доски представляет собой шестиугольник , состоящий из шести вершин (шести клеток шахматной доски), соединенных шестью ребрами (парами неатакующих клеток).
  • Комплекс (3,4)-шахматной доски — это триангуляция тора с 24 треугольниками (тройками неатакующих квадратов), 36 ребрами и 12 вершинами. Шесть треугольников встречаются в каждой вершине в том же шестиугольном узоре, что и комплекс (2,3)-шахматной доски.
  • Комплекс (4,5)-шахматной доски образует трехмерное псевдомногообразие : в окрестности каждой вершины встречаются 24 тетраэдра в форме тора, а не сферической формы, которая требовалась бы для многообразия . Если вершины удалить из этого пространства, результату можно придать геометрическую структуру в виде каспированного гиперболического 3-многообразия , топологически эквивалентного дополнению зацепления 20-компонентного зацепления .

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

Каждая грань содержит элементы. Следовательно, размерность равна . Δ m , n {\displaystyle \Delta _{m,n}} min ( m , n ) {\displaystyle \min(m,n)} Δ m , n {\displaystyle \Delta _{m,n}} min ( m , n ) − 1 {\displaystyle \min(m,n)-1}

Гомотопическая связность комплекса шахматной доски по крайней мере (so ). [1] : Раздел 1  min ( m , n , m + n + 1 3 ) − 2 {\displaystyle \min \left(m,n,{\frac {m+n+1}{3}}\right)-2} η ≥ min ( m , n , m + n + 1 3 ) {\displaystyle \eta \geq \min \left(m,n,{\frac {m+n+1}{3}}\right)}

Числа Бетти шахматных комплексов равны нулю тогда и только тогда, когда . [5] : 200  Собственные значения комбинаторных лапласианов шахматного комплекса являются целыми числами. [5] : 193  b r − 1 {\displaystyle b_{r-1}} ( m − r ) ( n − r ) > r {\displaystyle (m-r)(n-r)>r}

Комплекс шахматной доски является -связным, где . [6] : 527  Группа гомологий является 3-группой экспоненты не более 9 и, как известно, является в точности циклической группой из 3 элементов, когда . [6] : 543–555  ( ν m , n − 1 ) {\displaystyle (\nu _{m,n}-1)} ν m , n := min { m , n , ⌊ m + n + 1 3 ⌋ } {\displaystyle \nu _{m,n}:=\min\{m,n,\lfloor {\frac {m+n+1}{3}}\rfloor \}} H ν m , n ( M m , n ) {\displaystyle H_{\nu _{m,n}}(M_{m,n})} m + n ≡ 1 ( mod 3 ) {\displaystyle m+n\equiv 1{\pmod {3}}}

-скелет комплекса шахматной доски является вершинно разложимым в смысле Прована и Биллеры (и, таким образом, может быть разложен на части), и весь комплекс является вершинно разложимым, если . [7] : 3  Как следствие, любая позиция из k ладей на шахматной доске размером m на n , где , может быть преобразована в любую другую позицию, используя не более одного хода ладьей (где каждая промежуточная позиция также не является взятием ладьи). [7] : 3  ( ⌊ n + m + 1 3 ⌋ − 1 ) {\displaystyle (\lfloor {\frac {n+m+1}{3}}\rfloor -1)} n ≥ 2 m − 1 {\displaystyle n\geq 2m-1} k ≤ ⌊ m + n + 1 3 ⌋ {\displaystyle k\leq \lfloor {\frac {m+n+1}{3}}\rfloor } m n − k {\displaystyle mn-k}

Обобщения

Комплекс является "комплексом шахматной доски", определенным для k -мерной шахматной доски. Эквивалентно, это множество паросочетаний в полном k -дольном гиперграфе . Этот комплекс является по крайней мере -связным, для [1] : 33  Δ n 1 , … , n k {\displaystyle \Delta _{n_{1},\ldots ,n_{k}}} ( ν − 2 ) {\displaystyle (\nu -2)} ν := min { n 1 , ⌊ n 1 + n 2 + 1 3 ⌋ , … , ⌊ n 1 + n 2 + ⋯ + n k + 1 2 k + 1 ⌋ } {\displaystyle \nu :=\min\{n_{1},\lfloor {\frac {n_{1}+n_{2}+1}{3}}\rfloor ,\dots ,\lfloor {\frac {n_{1}+n_{2}+\dots +n_{k}+1}{2k+1}}\rfloor \}}

Ссылки

  1. ^ abcd Бьёрнер, А.; Ловас, Л.; Вречица, СТ; Живальевич, RT (1 февраля 1994 г.). «Шахматные комплексы и согласующие комплексы». Журнал Лондонского математического общества . 49 (1): 25–39 . doi :10.1112/jlms/49.1.25.
  2. ^ Вречица, Синиша Т.; Живальевич, Раде Т. (01 октября 2011 г.). «Шахматные комплексы неукротимые». Журнал комбинаторной теории . Серия А. 118 (7): 2157–2166 . arXiv : 0911.3512 . дои : 10.1016/j.jcta.2011.04.007 . ISSN  0097-3165.
  3. ^ Матоушек, Йиржи (2007). Использование теоремы Борсука-Улама : Лекции по топологическим методам в комбинаторике и геометрии (2-е изд.). Берлин-Гейдельберг: Springer-Verlag. ISBN 978-3-540-00362-5. Написано в сотрудничестве с Андерсом Бьёрнером и Гюнтером М. Циглером.
  4. ^ Goerner, Matthias Rolf Dietrich (2011). "1.2.2 Связь с комплексом шахматной доски 4 × 5". Визуализация регулярных мозаик: главные конгруэнтные связи и эквивариантные морфизмы с поверхностей на 3-многообразия (PDF) (докторская диссертация). Калифорнийский университет в Беркли.
  5. ^ ab Фридман, Джоэл; Хэнлон, Фил (1998-09-01). «О числах Бетти шахматных комплексов». Журнал алгебраической комбинаторики . 8 (2): 193– 203. doi :10.1023/A:1008693929682. hdl : 2027.42/46302 . ISSN  1572-9192.
  6. ^ ab Shareshian, John; Wachs, Michelle L. (2007-07-10). «Крутение в комплексе соответствия и шахматном комплексе». Advances in Mathematics . 212 (2): 525–570 . arXiv : math/0409054 . doi : 10.1016/j.aim.2006.10.014 . ISSN  0001-8708.
  7. ^ ab Циглер, Гюнтер М. (1992-09-23). ​​«Оболочкообразуемость шахматных комплексов».
Retrieved from "https://en.wikipedia.org/w/index.php?title=Chessboard_complex&oldid=1171501897"