Шахматный комплекс

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

Определения

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

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

Другое определение - это набор всех паросочетаний в полном двудольном графе. $K_{m,n}$ . ^[1]

Примеры

В любом ( 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-компонентной связи .

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

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

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

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

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

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

Обобщения

Комплекс $\Delta _{n_{1},\ldots ,n_{k}}$ представляет собой «шахматный комплекс», определенный для k -мерной шахматной доски. Эквивалентно, это набор паросочетаний в полном k -частном гиперграфе . Этот комплекс как минимум $(\nu -2)$ -связанный, для $\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]^: 33

Ссылки

^ Jump up to: ^а ^б ^с ^д Бьёрнер, А.; Ловас, Л.; Вречица, СТ; Живальевич, RT (1 февраля 1994 г.). «Шахматные комплексы и согласующие комплексы» . Журнал Лондонского математического общества . 49 (1): 25–39. дои : 10.1112/jlms/49.1.25 .
^ Вречица, Синиша Т.; Живальевич, Раде Т. (01 октября 2011 г.). «Шахматные комплексы неукротимые» . Журнал комбинаторной теории . Серия А. 118 (7): 2157–2166. arXiv : 0911.3512 . дои : 10.1016/j.jcta.2011.04.007 . ISSN 0097-3165 .
^ Матушек, Иржи (2007). Использование теоремы Борсука-Улама : Лекции по топологическим методам в комбинаторике и геометрии (2-е изд.). Берлин-Гейдельберг: Springer-Verlag. ISBN 978-3-540-00362-5 . Написано в сотрудничестве с Андерсом Бьёрнером и Гюнтером М. Циглером.
^ Гернер, Маттиас Рольф Дитрих (2011). «1.2.2 Связь с комплексом шахматной доски 4 × 5». Визуализация регулярных тесселяций: основные конгруэнтные связи и эквивариантные морфизмы от поверхностей к 3-многообразиям (PDF) (докторская диссертация). Калифорнийский университет, Беркли.
^ Jump up to: ^а ^б Фридман, Джоэл; Хэнлон, Фил (1 сентября 1998 г.). «О числах Бетти шахматных комплексов» . Журнал алгебраической комбинаторики . 8 (2): 193–203. дои : 10.1023/А:1008693929682 . hdl : 2027.42/46302 . ISSN 1572-9192 .
^ Jump up to: ^а ^б Шарешян, Джон; Вакс, Мишель Л. (10 июля 2007 г.). «Кручение в согласующем комплексе и шахматном комплексе» . Достижения в математике . 212 (2): 525–570. arXiv : math/0409054 . дои : 10.1016/j.aim.2006.10.014 . ISSN 0001-8708 .
^ Jump up to: ^а ^б Циглер, Гюнтер М. (23 сентября 1992 г.). «Обстреливаемость шахматных комплексов» .

[:0-1] Jump up to: ^а ^б ^с ^д Бьёрнер, А.; Ловас, Л.; Вречица, СТ; Живальевич, RT (1 февраля 1994 г.). «Шахматные комплексы и согласующие комплексы» . Журнал Лондонского математического общества . 49 (1): 25–39. дои : 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 .

[:03-3] Матушек, Иржи (2007). Использование теоремы Борсука-Улама : Лекции по топологическим методам в комбинаторике и геометрии (2-е изд.). Берлин-Гейдельберг: Springer-Verlag. ISBN 978-3-540-00362-5 . Написано в сотрудничестве с Андерсом Бьёрнером и Гюнтером М. Циглером.

[4] Гернер, Маттиас Рольф Дитрих (2011). «1.2.2 Связь с комплексом шахматной доски 4 × 5». Визуализация регулярных тесселяций: основные конгруэнтные связи и эквивариантные морфизмы от поверхностей к 3-многообразиям (PDF) (докторская диссертация). Калифорнийский университет, Беркли.

[:1-5] Jump up to: ^а ^б Фридман, Джоэл; Хэнлон, Фил (1 сентября 1998 г.). «О числах Бетти шахматных комплексов» . Журнал алгебраической комбинаторики . 8 (2): 193–203. дои : 10.1023/А:1008693929682 . hdl : 2027.42/46302 . ISSN 1572-9192 .

[:2-6] Jump up to: ^а ^б Шарешян, Джон; Вакс, Мишель Л. (10 июля 2007 г.). «Кручение в согласующем комплексе и шахматном комплексе» . Достижения в математике . 212 (2): 525–570. arXiv : math/0409054 . дои : 10.1016/j.aim.2006.10.014 . ISSN 0001-8708 .

[:3-7] Jump up to: ^а ^б Циглер, Гюнтер М. (23 сентября 1992 г.). «Обстреливаемость шахматных комплексов» .

[1]

[2]

[3]

[4]

[5]

[6]

[7]