Cтраница 2
Рассматривая четверку x vi v yi, мы видим, что вершина у должна быть смежной с одной из вершин v и v - Но у не может быть смежной с t) 2, так как вершины и и v разобщены. Это невозможно, поскольку, согласно предположению, множество N ( x) может быть покрыто двумя полными графами. [16]
Это число достигается тогда, когда каждый из графов Gt полный п имеет п, вершин. Построим вместо G другой граф G с тем же числом вершпп п компонент, заменяя GI и GI полными графами GI и G. Легко видеть, что ото увеличивает число ребер. Таким образом, максимальное число ребер должеи иметь граф, состоящий из k - 1 изолированных вершш. [17]
Доказательство теоремы 3.1.3. Эта теорема является простым следствием леммы 3.1.2. Если T ( G) нечетно, то очевидно, что G - полный граф. Если K ( G) четно, то пусть S - множество, определенное в лемме 3.1.2, a GI, , Gt - компоненты связности графа G - S. Как следует из предыдущей леммы, они являются полными графами. [18]
Поскольку полностью подходящая когомология тривиальна, то это, таким образом, есть кограница 1-коцепи, а последнее, будучи функцией пар в Z2, являет собой граф; тройки два-графа являются носителями нечетного числа ребер этого графа. Две 1-коцепи имеют одну и ту же кограницу тогда и только тогда, когда они отличаются на 1-коцикл, то есть кограницу 0-коцепи ( функцию из точечного множества в Z2); это означает существование разбиения точечного множества Х [) Y и двух графов, согласованных внутри X и внутри У и являющихся дополнительными между этими множествами. В терминологии Зейделя эти графы являются связанными по переключению относительно разбиения XJY. Таким образом, два-граф эквивалентен переключательному классу графов. Пустой два-граф соответствует переключательному классу полных двудольных графов, а полный два-граф - двум полным графам. Эти случаи исключаются из дальнейшего рассмотрения. [19]
Очень мало известно о классических числах Рамсея. Под этими числами принято понимать число вершин в наименьшем полном графе, который непременно содержит данное множество полных графов с меньшим числом вершин. Не существует известного эффективного алгоритма для нахождения классических чисел Рамсея. Известен лишь следующий рецепт: необходимо перебрать все возможные раскраски полных графов, постепенно увеличивая число вершин до тех пор, пока не будет получено число Рамсея. Трудность решения этой задачи возрастает экспоненциально, и задача быстро становится вычислительно неразрешимой. Еще меньше известно о том, кто выигрывает-первый или второй игрок, если в игре Рамсея придерживаться рациональной стратегии. Игру сим удалось проанализировать ( выигрывает второй игрок), но об играх Рамсея на полных графах с большим число вершин почти ничего не известно. [20]