Половина графика - Half graph

Полуграф с 14 вершинами

В теория графов, филиал математика, а половина графика это особый вид двудольный граф. Эти графы называются полуграфами, потому что они имеют примерно половину ребер полный двудольный граф на тех же вершинах. Название этим графикам дали Пол Эрдёш и Андраш Хайнал.^[1]

Определение

Чтобы определить половину графика на ${\displaystyle 2n}$ вершины ${\displaystyle u_{1},\dots u_{n}}$ и ${\displaystyle v_{1},\dots v_{n}}$, соединять ${\displaystyle u_{i}}$ к ${\displaystyle v_{j}}$ краем всякий раз, когда ${\displaystyle i\leq j}$.^[1]

То же самое понятие может быть определено таким же образом для бесконечных графов над двумя копиями любого упорядоченного набора вершин.^[1]Полуграф над натуральными числами (с их обычным порядком) обладает тем свойством, что каждая вершина ${\displaystyle v_{j}}$ имеет конечный степень, в большинстве ${\displaystyle j}$. Вершины по другую сторону двудольного деления имеют бесконечную степень.^[2]

Неправильность

Одно приложение для полуграфа происходит в Лемма Семереди о регулярности, в котором говорится, что вершины любого графа могут быть разбиты на постоянное количество подмножеств равного размера, так что большинство пар подмножеств являются регулярными (ребра, соединяющие пару, ведут себя определенным образом как случайный граф определенной плотности). Если половину графа таким образом разбить на ${\displaystyle k}$ подмножеств, количество нерегулярных пар будет как минимум пропорционально ${\displaystyle k}$. Следовательно, невозможно усилить лемму о регулярности, чтобы показать существование разбиения, для которого все пары регулярны.^[3]

Соответствие

Полуграф имеет уникальный идеальное соответствие. В этом нетрудно убедиться по индукции: ${\displaystyle u_{n}}$ должен соответствовать своему единственному соседу, ${\displaystyle v_{n}}$, а остальные вершины образуют еще один полуграф. Более того, каждый двудольный граф с уникальным идеальным паросочетанием является подграфом полуграфа.^[4]

В графиках несчетного хроматического числа

Если хроматическое число графа бесчисленный, то граф обязательно содержит в качестве подграфа полуграф на натуральных числах. Этот полуграф, в свою очередь, содержит все полный двудольный граф в котором одна сторона двудольного деления конечна, а другая - счетно бесконечна.^[5]

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

1. Эрдеш, Пол (1984), «Некоторые комбинаторные, геометрические и теоретико-множественные проблемы теории меры», Kölzow, D .; Махарам-Стоун, Д. (ред.), Теория меры Обервольфах 1983, Конспект лекций по математике, 1089, Springer
2. Нешетржил, Ярослав; Шела, Сахарон (2003), «О порядке счетных графов», Европейский журнал комбинаторики, 24 (6): 649–663, arXiv:математика / 0404319, Дои:10.1016 / S0195-6698 (03) 00064-7, МИСТЕР  1995579
3. Конлон, Дэвид; Фокс, Джейкоб (2012), «Границы регулярности графов и леммы об удалении», Геометрический и функциональный анализ, 22 (5): 1191–1256, arXiv:1107.4829, Дои:10.1007 / s00039-012-0171-х, МИСТЕР  2989432
4. Годсил, К. Д. (1985), «Перевернутые деревья», Комбинаторика, 5 (1): 33–39, Дои:10.1007 / bf02579440. См., В частности, лемму 2.1.
5. Эрдеш, Пол; Хайнал, Андраш (1985), «Хроматическое число конечных и бесконечных графов и гиперграфов» (PDF), Дискретная математика, 53: 281–285, Дои:10.1016 / 0012-365X (85) 90148-7, МИСТЕР  0786496. Результат о том, что графы несчетного хроматического числа содержат бесконечную половину графа, приписывается в этой статье Хайналу и цитируется в статье 1973 года тех же авторов с Шелахом, но в этой статье результат сформулирован только в более слабой форме, чем графы несчетного хроматического числа. содержат полные двудольные графы, одна сторона которых - любое конечное число, а другая - бесконечность.