Игра Мешулам - Википедия - Meshulams game

В теория графов, Игра Мешулама это игра, используемая для объяснения теоремы Роя Мешулама^[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 я гамма (G) geq k}$, тогда ${ Displaystyle пси (G) geq k}$. Доказательство: Позволять А быть независимым множеством с числом доминирования не менее k. CON начинается с предложения всех граней (а,б) куда а в А. Если NON разъединяет все такие ребра, то вершины А остаются изолированными, поэтому оценка CON бесконечна. Если NON взрывает такое ребро, то взрыв удаляется из А только вершины, которые смежны б (взрыв на а не разрушает вершины А, поскольку A - независимое множество). Следовательно, оставшиеся вершины А требуется по крайней мере k-1 вершина для доминирования, поэтому число доминирования А уменьшилось не более чем на 1. Следовательно, NON требует как минимум k взрывы, чтобы уничтожить все вершины A. Это доказывает, что ${ Displaystyle пси (G) geq я гамма (G)}$.

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

4. Если грамм это полный двудольный граф K_{п, п}, тогда ${ Displaystyle пси (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 пси (г) 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)}$.

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

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

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