Мешулам игра - Meshulams game - Wikipedia

В теория графов, Игра Мешулама это игра, используемая для объяснения теоремы Роя Мешулама^[1] связанный с гомологическая связность из комплекс независимости графа, который является наименьшим индексом k такие, что все редуцированные гомологические группы вплоть до k тривиальны. Формулировка этой теоремы как игры принадлежит Ахарони, Бергеру и Зиву.^[2][3]

Описание

Игровая доска - это график ГРАММ. Это игра с нулевой суммой для двух игроков CON и NON. КОН хочет показать, что я (грамм), комплекс независимости из грамм, имеет высокий возможность подключения; NON хочет доказать обратное.

В свою очередь КОН выбирает преимущество. е из оставшегося графика. Затем NON выбирает один из двух вариантов:

• Отключение - убрать край е из графика.
• Взрыв - удалить обе конечные точки евместе со всеми их соседями и инцидентными им краями.

Оценка CON определяется следующим образом:

• Если в какой-то момент оставшийся граф имеет изолированную вершину, счет равен бесконечности;
• В противном случае в какой-то момент оставшийся граф не содержит вершины; в этом случае счет - это количество взрывов.

Для каждого данного графа грамм, то ценность игры на грамм (т. е. оценка CON при оптимальной игре обеих сторон) обозначается как Ψ(грамм).

Ценность игры и гомологическая взаимосвязь

Мешулам^[1] доказал, что для каждого графа грамм:

${\displaystyle \eta _{H}(I(G))\geq \Psi (G)}$

куда ${\displaystyle \eta _{H}(I(G))}$ является гомологической связностью ${\displaystyle I(G)}$ плюс 2.

Примеры

1. Яж грамм имеет k связанные компоненты, то Ψ(грамм) ≥ k. Независимо от порядка, в котором CON предлагает ребра, каждый взрыв, сделанный NON, уничтожает вершины в одном компоненте, поэтому NON требует как минимум k взрывы, чтобы уничтожить все вершины.

2. Если грамм это союз k вершинно-непересекающиеся клики, каждая из которых содержит не менее двух вершин, то Ψ(грамм) = k, поскольку каждый взрыв полностью уничтожает одну клику.

3. Если грамм имеет независимость число господства по крайней мере k, ${\displaystyle i\gamma (G)\geq k}$, тогда ${\displaystyle \Psi (G)\geq k}$. Доказательство: Позволять А быть независимым множеством с числом доминирования не менее k. CON начинается с предложения всех граней (а,б) куда а в А. Если NON разъединяет все такие ребра, то вершины А остаются изолированными, поэтому оценка CON бесконечна. Если NON взрывает такое ребро, то взрыв удаляется из А только вершины, которые смежны б (взрыв на а не разрушает вершины А, поскольку A - независимое множество). Следовательно, оставшиеся вершины А требуется по крайней мере k-1 вершина для доминирования, поэтому число доминирования А уменьшилось не более чем на 1. Следовательно, NON требует как минимум k взрывы, чтобы уничтожить все вершины A. Это доказывает, что ${\displaystyle \Psi (G)\geq i\gamma (G)}$.

• Примечание: это также означает, что ${\displaystyle \Psi (L(G))\geq \nu (G)/2}$, куда ${\displaystyle L(G)}$ это линейный график группы G и ${\displaystyle \nu (G)}$ это размер наибольшего соответствия в грамм. Это потому, что совпадения в грамм независимые множества в L(грамм). Каждый край в грамм является вершиной в L (грамм), и он доминирует не более чем на двух ребрах в сопоставлении (= вершинах в независимом множестве). ^[3]
• Аналогично, когда ЧАС является р-дольный гиперграф, ${\displaystyle \Psi (L(H))\geq \nu (H)/r}$.^[4]

4. Если грамм это полный двудольный граф K_{п, п}, тогда ${\displaystyle \Psi (L(G))\geq \lfloor 2n/3\rfloor }$.^[5][6] Доказательство: L (грамм) можно рассматривать как массив ячеек размером n на n, где каждая строка является вершиной с одной стороны, каждый столбец является вершиной с другой стороны, а каждая ячейка является ребром. На графике L(грамм) каждая ячейка является вершиной, а каждое ребро представляет собой пару из двух ячеек в одном столбце или одной строке. CON начинается с предложения двух ячеек в одном ряду; если NON взрывает их, тогда CON предлагает две ячейки в одном столбце; если NON взрывает их снова, то два взрыва вместе разрушают 3 строки и 3 столбца. Следовательно, по крайней мере ${\displaystyle \lfloor 2n/3\rfloor }$ взрывы необходимы для удаления всех вершин.

• Примечание: этот результат был позже обобщен: если F любой подграф K_{п, п}, тогда ${\displaystyle \Psi (L(G))\geq {\frac {|F|}{n}}-{\frac {n}{3}}-{\frac {1}{2}}}$.^[3]:Thm.3.10

Доказательство для случая 1

Чтобы проиллюстрировать связь между игрой Мешулама и связью, мы докажем это в частном случае, когда ${\displaystyle \eta _{H}(I(G))=1}$, что является наименьшим возможным значением ${\displaystyle \eta _{H}(I(G))}$. Докажем, что в этом случае ${\displaystyle \Psi (G)\leq 1}$, т.е. NON всегда может уничтожить весь граф, используя не более одного взрыва.

${\displaystyle \eta _{H}(I(G))=1}$ Значит это ${\displaystyle I(G)}$ не связано. Это означает, что есть два подмножества вершин, Икс и Y, где нет края в ${\displaystyle I(G)}$ соединяет любую вершину X с любой вершиной Y. Но ${\displaystyle I(G)}$ это комплекс независимости из грамм; так в грамм, каждая вершина Икс соединяется с каждой вершиной Y. Независимо от того, как играет CON, он должен на каком-то этапе выбрать ребро между вершиной Икс и вершина Y. NON может взорвать это ребро и уничтожить весь граф.

В общем, доказательство работает только одним способом, то есть могут быть графы, для которых ${\displaystyle \eta _{H}(I(G))>\Psi (G)}$.

Смотрите также

• Теоремы холловского типа для гиперграфов

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

1. Мешулам, Рой (2003-05-01). «Доминирование чисел и гомология». Журнал комбинаторной теории, серия А. 102 (2): 321–330. Дои:10.1016 / S0097-3165 (03) 00045-1. ISSN  0097-3165.
2. Ахарони, Рон; Бергер, Эли; Зив, Ран (2007-05-01). «Независимые системы представителей в взвешенных графах». Комбинаторика. 27 (3): 253–267. Дои:10.1007 / s00493-007-2086-у. ISSN  0209-9683. S2CID  43510417.
3. Ахарони, Рон; Бергер, Эли; Котлар, Дани; Зив, Ран (2017-01-04). «По догадке Штейна». Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. 87 (2): 203–211. Дои:10.1007 / s12188-016-0160-3. ISSN  0025-5858. S2CID  119139740.
4. Хакселл, Пенни; Наринс, Лотар; Сабо, Тибор (1 августа 2018 г.). «Экстремальные гиперграфы для гипотезы Райзера». Журнал комбинаторной теории, серия А. 158: 492–547. Дои:10.1016 / j.jcta.2018.04.004. ISSN  0097-3165.
5. Björner, A .; Lovász, L .; Vrećica, S.T .; Живалевич, Р. Т. (1994). «Комплексы шахматной доски и сопрягающие комплексы». Журнал Лондонского математического общества. 49 (1): 25–39. Дои:10.1112 / jlms / 49.1.25. ISSN  1469-7750.
6. Шарешян, Джон; Вакс, Мишель Л. (2009-10-01). "Топ-гомологии гиперграфов комплексов согласования, p-цикловых комплексов и комплексов Квиллена симметрических групп". Журнал алгебры. 322 (7): 2253–2271. arXiv:0808.3114. Дои:10.1016 / j.jalgebra.2008.11.042. ISSN  0021-8693. S2CID  5259429.