299
правок
Изменения
→Случай произвольного графа
===Случай произвольного графа===
Теорема 1С.6. Для щствольного графа Н существует рамсеевский граф,
Доказательство. Пусть к — v(H), п — г(к,к). Пронумеруем Еершины графа Н. Построим граф G0 следующим образсм: разместим его вершины е виде таблице п х Ск. Таким образом в каждом столбце Еершины окажутся пронумерованы числами ст 1 до п. как соответствующие строки таблицы. Е каждом столбце одним из Ск способов разместим граф Н (каждый столбец соответствует одному из возможных споссбсЕ размещения). Все рёбра графа G0 будут рёбрами указанных копий графа Н, Граф G0 является п-дсльным, егс естественное разбиение на доли задаётся таблицей: V^(G°) — это вершины, соответствующие г ряду таблицы. Мы последовательно е несколько шагов будем нерестраивать наш граф с помощью леммы 1С.З так. чтобы вершины последующих графов также разбивались на п долей и записывались в виде таблицы. Каждый шаг будет состЕСтстЕСвать однсй паре строк таблицы,
Шаг перестройки графа.
Итак, пусть мы имеем n-дольный граф Ge, доли которого К = К(Сг) (где г 6 [1--п]) Пусть с парой строк (и. соответственно, долей) i,j мы еше не выполняли шаг. Очеьидно, граф Gitj = Gt{Vi\JVj) дЕудолен и для него не лемме 10.3 сушестЕует двудольный рамсееЕОкий граф Pitj. Еолее того если вершины Р^- разбиты на дес доли Wi и Wj. тс для любой раскраски рёбер в два цЕета существует одвснветнсе Есгружение (р графа Gitj е Pitj в котором (p(Vj) С Wi и ip(Vj) С Wj Назовём таксе погружение одноцветным.
Перейдём к построению Ge+1. Заменим К на Wi и Vj на Wj. проведём между зтими долями Есе рёбра графа Pitj. Наша цель в тем, чтобы для любого погружения Gitj в Р^ была содержащая его кспия Ge (причём доли этой копии лежали в соответствующих строках таблицы графа
занумеруем всевозможные погружения Gij в Pitj: пусть это Gjj(l),... Gij{q). Каждому погружению Gitj(s) мы поставим в соответствие отдельные кспии Есех отличных ст Vj, и Vj долей: Vi(s),..., Vn(s). Положим Vi(s) = V(Gij(s))nWi и Vj(s) = V(Gij(s))r\Wj. На зтих долях построим копию графа Ge В результате для каждого погружения графа Gitj в Pitj мы построили свею копию графа Ge.
Выделение одноцветного индуцированного подграфа.
Итак, докажем, что G = Gc" и есть рамсеевский граф для Н. Пусть Ри - ■ ■ iPci — именно такая нумерация пар строк в нашей таблице, ь порядке которой совершались шаги перестройки графа. Еассмстрим произвольную раскраску рёбер р графа G ь два цвета и докажем следующий факт.
Для каждссс £ е [0..С2] существует изоморфные G1 иьсуьирсван-
ный поограф графа G. б котором для пар строк ре+г- .., рс% все рёбра между вершинами ссответстеукших пар строк в раскраске р одноцветны
Доказательство. Индукция с обратным ходом ст £ — С2п к £ — 0. База для £ = С\ очеЕидна. Докажем переход £ ^ £ — 1
Итак рассмотрим наш изоморфный G1 подграф который мы для простоты будем обозначать Ge и пару строку е нем пусть это строки г и j. a Pij и Gitj — те двудольные графы между этими строками, что списаны в шаге псстроения. Так как Pjj (подграф графа Ge) — рамссеЕСкий граф для Gij. мы межем выбрать одноцветное е раскраске р погружение Gij в Pitj и соответствующая ему по построению копия Ge_1 будет искомым (из построения очевидно, чте индуиирсьанным!) подграфом Ge а значит, bG □
Таким образом, сушестнует иземерфный G0 индуцированный подграф графа G. е кстсрем для каждой пары стрск i,j Есе ребра между Есршинами состЕСтстЕуюших строк одноцветны е раскраске р. Будем обозначать зтот граф просто G0. Бассмстрим граф Кп Еершины которого соответствуют строкам таблицы и искрасим каждое ребро в пест в который покрашены рёбра G0 между соответствующими строками Так как п = r(k,k) существуют к Есршин, между которыми ьсе рёбра одноцветны. Рассмотрим столбец графа G°, е котором Н размещён именно е строчках. соответствующих этим к вершинам. Подграф Н' графа G0 на вершинах этого столбца и соответствующих строчках из с мор фен Н пс построению является индугшрсЕанным подграфом графа G0 и все его рёбра одноцветны в раскраске р. Остаётся лишь заметить, что Я' — индуцированный подграф графа G. □
