В теории графов , разделе математики , полуграф - это особый тип двудольного графа . Эти графы называются полуграфами, потому что они имеют примерно половину ребер полного двудольного графа на тех же вершинах. Название этим графикам дали Пол Эрдёш и Андраш Хайнал . [1]
Определение [ править ]
Для того, чтобы определить пол граф на вершинах и подключить к ребру когда это . [1]
То же самое понятие может быть определено таким же образом для бесконечных графов над двумя копиями любого упорядоченного набора вершин. [1] Полуграф над натуральными числами (с их обычным порядком) обладает тем свойством, что каждая вершина имеет конечную степень , самое большее . Вершины по другую сторону двудольного деления имеют бесконечную степень. [2]
Неправильность [ править ]
Одно приложение для полуграфа встречается в лемме Семереди о регулярности , которая утверждает, что вершины любого графа могут быть разбиты на постоянное количество подмножеств равного размера, так что большинство пар подмножеств являются регулярными (ребра, соединяющие пару, ведут себя в определенными способами, такими как случайный граф определенной плотности). Если половину графа таким образом разбить на подмножества, количество неправильных пар будет как минимум пропорционально . Следовательно, невозможно усилить лемму о регулярности, чтобы показать существование разбиения, для которого все пары регулярны. [3]
Соответствие [ править ]
Половина графа имеет уникальное идеальное соответствие . В этом нетрудно убедиться по индукции: необходимо сопоставить его единственному соседу , а оставшиеся вершины образуют другой полуграф. Более того, каждый двудольный граф с уникальным идеальным паросочетанием является подграфом полуграфа. [4]
В графиках несчетного хроматического числа [ править ]
Если хроматическое число графа несчетное , то граф обязательно содержит в качестве подграфа половину графа на натуральных числах. Этот полуграф, в свою очередь, содержит каждый полный двудольный граф, в котором одна сторона двудольного деления конечна, а другая - счетно бесконечна. [5]
Ссылки [ править ]
- ^ a b c Erdős, Пауль (1984), "Некоторые комбинаторные, геометрические и теоретико-множественные проблемы теории меры", в Kölzow, D .; Maharam-Stone, D. (eds.), Measure Theory Oberwolfach 1983 , Lecture Notes in Mathematics, 1089 , Springer.
- ^ Нешетржил, Ярослав ; Сала, Saharon (2003), "О порядке счетных графов", Европейский журнал комбинаторике , 24 (6): 649-663, Arxiv : математика / 0404319 , DOI : 10.1016 / S0195-6698 (03) 00064-7 , MR 1995579
- ^ Конлон, Дэвид ; Фокс, Джейкоб (2012), "Граница для графа регулярности и удаления лемм", Геометрическая и функциональный анализ , 22 (5): 1191-1256, Arxiv : 1107,4829 , DOI : 10.1007 / s00039-012-0171-х , МР 2989432
- ^ Godsil, CD (1985), "обратны деревьев", Combinatorica , 5 (1): 33-39, DOI : 10.1007 / bf02579440 CS1 maint: обескураженный параметр ( ссылка ). См., В частности, лемму 2.1.
- ^ Erdős, Пол ; Хайнал, Андраш (1985), «Хроматическое число конечных и бесконечных графов и гиперграфов» (PDF) , Дискретная математика , 53 : 281–285, DOI : 10.1016 / 0012-365X (85) 90148-7 , MR 0786496 . Результат о том, что графы несчетного хроматического числа содержат бесконечную половину графа, приписывается в этой статье Хайналу и цитируется в статье 1973 года тех же авторов с Шелахом, но в этой статье результат сформулирован только в более слабой форме, чем графы несчетного хроматического числа. содержат полные двудольные графы, одна сторона которых - любое конечное число, а другая - бесконечное число.
