Теорема де Брейна – Эрдеша (теория графов)

Эта статья о раскраске бесконечных графов. Информацию о количестве линий, определяемых конечным набором точек, см. в теореме Де Брейна – Эрдеша (геометрия инцидентности) .

В теории графов теорема Де Брюйна-Эрдеша связывает раскраску бесконечного графа с той же проблемой на его конечных подграфах . Он утверждает, что, когда все конечные подграфы можно раскрасить в $c$ цвета, то же самое справедливо и для всего графа. Теорема была доказана Николаасом Говертом де Брейном и Полем Эрдешем ( 1951 ), в честь которых она названа.

Теорема Де Брейна-Эрдеша имеет несколько различных доказательств, каждое из которых так или иначе зависит от выбранной аксиомы . Его приложения включают распространение теоремы о четырех цветах и ​​теоремы Дилворта с конечных графов и частично упорядоченных множеств на бесконечные, а также сведение проблемы Хадвигера-Нельсона о хроматическом числе плоскости к проблеме о конечных графах. Его можно обобщить от конечного числа цветов до наборов цветов, мощность которых является сильно компактным кардиналом .

Определения и заявление

Неориентированный граф — математический объект, состоящий из набора вершин и набора ребер , соединяющих пары вершин. Две вершины, связанные с каждым ребром, называются его конечными точками. Граф конечен, если его вершины и ребра образуют конечные множества , и бесконечен в противном случае. связывает Раскраска графа каждую вершину с цветом, взятым из набора цветов, таким образом, что каждое ребро имеет два разных цвета в своих конечных точках. Частой целью раскраски графов является минимизация общего количества используемых цветов; хроматическое число графа — это минимальное количество цветов. Теорема о четырех цветах утверждает, что каждому конечному графу, который можно нарисовать без пересечений на евклидовой плоскости, требуется не более четырех цветов; однако для некоторых графиков с более сложной связностью требуется более четырех цветов. Следствием аксиомы выбора является то, что хроматическое число четко определено для бесконечных графов, но для этих графов хроматическое число само по себе может быть бесконечным кардинальным числом .

Подграф . графа — это другой граф, полученный из подмножества его вершин и подмножества его ребер Если больший граф раскрашен, ту же раскраску можно использовать и для подграфа. Следовательно, хроматическое число подграфа не может быть больше хроматического числа всего графа. Теорема Де Брюйна-Эрдеша касается хроматических чисел бесконечных графов и показывает, что (опять же, при условии выбора аксиомы) их можно вычислить на основе хроматических чисел их конечных подграфов. Он утверждает, что если хроматические числа конечных подграфов графа $G$ иметь конечное максимальное значение $c$, то хроматическое число $G$ сам по себе точно $c$. С другой стороны, если не существует конечной верхней границы хроматических чисел конечных подграфов графа $G$, то хроматическое число $G$ само должно быть бесконечным.

Приложения

Первоначальная мотивация Эрдеша при изучении этой проблемы заключалась в том, чтобы распространить с конечных на бесконечные графы теорему о том, что всякий раз, когда граф имеет ориентацию с конечной максимальной исходящей степенью, $k$, у него также есть $(2k+1)$-раскраска. Для конечных графов это следует из того, что такие графы всегда имеют вершину степени не выше $2k$, который можно раскрасить одним из $2k+1$ цвета после того, как все оставшиеся вершины будут окрашены рекурсивно. Бесконечные графы с такой ориентацией не всегда имеют вершину низкой степени (например, решетки Бете имеют $k=1$ но сколь угодно большой минимальной степенью), поэтому этот аргумент требует, чтобы граф был конечным. Но теорема Де Брейна–Эрдёша показывает, что $(2k+1)$-раскраска существует даже для бесконечных графов.

Семицветная раскраска плоскости и четыреххроматическое веретено Мозера, нарисованное в виде графа единичных расстояний на плоскости, обеспечивающее верхнюю и нижнюю оценки проблемы Хадвигера – Нельсона.

Другое применение теоремы Де Брюйна-Эрдёша относится к задаче Хадвигера-Нельсона , в которой задается вопрос, сколько цветов необходимо, чтобы раскрасить точки евклидовой плоскости так, чтобы каждые две точки, находящиеся на расстоянии единицы друг от друга, имели разные цвета. Это задача о раскраске бесконечного графа, у которого есть вершина для каждой точки плоскости и ребро для каждых двух точек, евклидово расстояние которых равно единице. этого Индуцированные подграфы графа называются графами единичных расстояний . Граф единичных расстояний с семью вершинами, веретено Мозера , требует четырех цветов; в 2018 году были обнаружены гораздо более крупные графики единичных расстояний, для которых требуется пять цветов. Весь бесконечный граф имеет известную раскраску в семь цветов, основанную на шестиугольном замощении плоскости. Следовательно, хроматическое число плоскости должно быть либо 5, 6 или 7, но неизвестно, какое из этих трех чисел является правильным значением. Теорема Де Брейна-Эрдёша показывает, что для этой задачи существует конечный граф единичных расстояний с тем же хроматическим числом, что и вся плоскость, поэтому, если хроматическое число больше пяти, этот факт можно доказать с помощью конечного вычисления.

Теорема Де Брейна-Эрдёша также может быть использована для расширения теоремы Дилворта от конечных до бесконечных частично упорядоченных множеств . Теорема Дилворта утверждает, что ширина частичного порядка (максимальное количество элементов в наборе взаимно несравнимых элементов) равна минимальному количеству цепочек ( полностью упорядоченных подмножеств), на которые может быть разбит частичный порядок. Разбиение на цепочки можно интерпретировать как раскраску графа несравнимости частичного порядка. Это граф, имеющий вершину для каждого элемента порядка и ребро для каждой пары несравнимых элементов. Используя эту интерпретацию раскраски вместе с отдельным доказательством теоремы Дилворта для конечных частично упорядоченных множеств, можно доказать, что бесконечное частично упорядоченное множество имеет конечную ширину. $w$ тогда и только тогда, когда он имеет раздел на $w$ цепи.

Точно так же теорема Де Брейна–Эрдеша расширяет теорему о четырех цветах с конечных плоских графов на бесконечные плоские графы. Любой конечный планарный граф можно раскрасить в четыре цвета по теореме о четырех цветах. Теорема Де Брейна-Эрдёша показывает, что любой граф, который можно нарисовать без пересечений на плоскости, конечной или бесконечной, можно раскрасить в четыре цвета. В более общем смысле, каждый бесконечный граф, все конечные подграфы которого плоские, снова может быть четырехцветным.

Доказательства

В оригинальном доказательстве теоремы Де Брейна-Эрдёша Де Брейна использовалась трансфинитная индукция .

Готшалк (1951) предоставил следующее очень краткое доказательство, основанное на Тихонова о теореме компактности в топологии. Предположим, что для данного бесконечного графа $G$, каждый конечный подграф $k$-раскрашиваем, и пусть $X$ быть пространством всех заданий $k$ цвета вершинам $G$ (независимо от того, образуют ли они допустимую раскраску). Затем $X$ может быть задана топология как пространство продукта $k^{V(G)}$, где $V(G)$ обозначает множество вершин графа. По теореме Тихонова это топологическое пространство компактно . Для каждого конечного подграфа $F$ из $G$, позволять $X_{F}$ быть подмножеством $X$ состоящий из назначений цветов, которые правильно окрашивают $F$. Тогда система множеств $X_{F}$ — семейство замкнутых множеств со свойством конечного пересечения , поэтому по компактности оно имеет непустое пересечение. Каждый член этого пересечения является допустимой раскраской $G$.

Другое доказательство с использованием леммы Цорна было дано Лайошем Посой , а также в докторской диссертации 1951 года. диссертация Габриэля Эндрю Дирака . Если $G$ — бесконечный граф, в котором каждый конечный подграф является $k$-раскрашиваема, то по лемме Цорна это подграф максимального графа $M$ с тем же свойством (к которому нельзя добавить больше ребер, не заставляя какой-либо конечный подграф требовать больше, чем $k$ цвета). Бинарное отношение несмежности в $M$ является отношением эквивалентности , и его классы эквивалентности обеспечивают $k$-раскраска $G$. Однако это доказательство труднее обобщить, чем доказательство компактности.

Теорему также можно доказать с помощью ультрафильтров или нестандартный анализ . Нэш-Вильямс (1967) дает доказательство для графов со счетным числом вершин на основе леммы Кенига о бесконечности .

Зависимость от выбора

Все доказательства теоремы Де Брейна-Эрдеша используют ту или иную форму аксиомы выбора . Некоторая форма этого предположения необходима, поскольку существуют модели математики, в которых как аксиома выбора, так и теорема Де Брюйна – Эрдеша неверны. Точнее, Мисельский (1961) показал, что эта теорема является следствием булевой теоремы о простых идеалах , свойства, которое подразумевается аксиомой выбора, но более слабым, чем полная аксиома выбора, а Лойхли (1971) показал, что Де Брюйн – Теорема Эрдеша и булева теорема о простых идеалах эквивалентны по аксиоматической силе. Можно также показать, что теорема Де Брейна-Эрдёша для счетных графов эквивалентна по аксиоматической силе в рамках некоторой теории арифметики второго порядка слабой лемме Кёнига.

В качестве контрпримера к теореме в моделях теории множеств без выбора пусть $G$ — бесконечный граф, вершины которого представляют все возможные действительные числа. В $G$, соедините каждые два действительных числа $x$ и $y$ краем всякий раз, когда одно из значений $|x-y|\pm {\sqrt {2}}$ является рациональным числом . Эквивалентно, в этом графе ребра существуют между всеми действительными числами. $x$ и все действительные числа вида $x+q\pm {\sqrt {2}}$, для рациональных чисел $q$. Каждый путь в этом графе, начиная с любого действительного числа $x$, чередуется между числами, которые отличаются от $x$ на рациональное число плюс четное кратное ${\sqrt {2}}$ и числа, отличающиеся от $x$ на рациональное число плюс нечетное кратное ${\sqrt {2}}$. Такое чередование предотвращает $G$ не содержит циклов нечетной длины, поэтому каждый из его конечных подграфов требуется всего два цвета. Однако в модели Соловея , в которой каждый набор действительных чисел измерим по Лебегу , $G$ требует бесконечно много цветов, поскольку в этом случае каждый цветовой класс должен быть измеримым множеством, и можно показать, что каждое измеримое множество действительных чисел без ребер $G$ должна иметь нулевую меру. Следовательно, в модели Соловея (бесконечное) хроматическое число всех $G$ много больше хроматического числа его конечных подграфов (не более двух).

Обобщения

Радо (1949) доказывает следующую теорему, которую можно рассматривать как обобщение теоремы Де Брейна – Эрдеша. Позволять $V$ быть бесконечным множеством, например множеством вершин бесконечного графа. Для каждого элемента $v$ из $V$, позволять $c_{v}$ быть конечным набором цветов. Кроме того, для любого конечного подмножества $S$ из $V$, выберите какую-то конкретную раскраску $C_{S}$ из $S$, в котором цвет каждого элемента $v$ из $S$ принадлежит $c_{v}$. Тогда существует глобальная раскраска $\chi$ из всех $V$ с тем свойством, что каждое конечное множество $S$ имеет конечное надмножество $T$ на котором $\chi$ и $C_{T}$ соглашаться. В частности, если мы выберем $k$-раскраска для каждого конечного подграфа бесконечного графа $G$, то есть $k$-раскраска $G$ в котором каждый конечный граф имеет больший суперграф, раскраска которого совпадает с раскраской всего графа.

Если граф не имеет конечного хроматического числа, то из теоремы Де Брейна–Эрдёша следует, что он должен содержать конечные подграфы каждого возможного конечного хроматического числа. Исследователи также исследовали другие условия на подграфах, которые вынуждены возникать в этом случае. Например, неограниченно хроматические графы также должны содержать все возможные конечные двудольные графы в качестве подграфа . Однако они могут иметь сколь угодно большой нечетный обхват и, следовательно, могут избегать любого конечного набора недвудольных подграфов.

Теорема Де Брейна-Эрдеша также применима непосредственно к задачам раскраски гиперграфов , где требуется, чтобы каждое гиперребро имело вершины более чем одного цвета. Что касается графов, гиперграф имеет $k$-раскраска тогда и только тогда, когда каждый из его конечных подгиперграфов имеет $k$-раскраска. Это частный случай компактности о теоремы Курта Гёделя , утверждающей, что набор предложений первого порядка имеет модель тогда и только тогда, когда каждое конечное подмножество имеет модель. его Более конкретно, теорему Де Брейна-Эрдеша можно интерпретировать как компактность структур первого порядка , нелогическими значениями которых является любой конечный набор цветов и единственным предикатом этих значений является неравенство.

Теорему также можно обобщить на ситуации, в которых количество цветов является бесконечным кардинальным числом . Если $\kappa$ — сильно компактный кардинал , то для любого графа $G$ и кардинальное число $\mu <\kappa$, $G$ имеет не более хроматического числа $\mu$ тогда и только тогда, когда каждый из его подграфов мощности меньше $\kappa$ имеет не более хроматического числа $\mu$. Исходная теорема Де Брейна–Эрдёша имеет место $\kappa =\aleph _{0}$ этого обобщения, поскольку множество конечно тогда и только тогда, когда его мощность меньше $\aleph _{0}$. Однако необходимо некоторое предположение, например, о сильно компактном кардинале: если обобщенная гипотеза континуума верна, то для каждого бесконечного кардинала $\gamma$, существует граф $G$ мощности $(2^{\gamma })^{+}$ такая, что хроматическое число $G$ больше, чем $\gamma$, но такой, что каждый подграф $G$ чей набор вершин имеет меньшую мощность, чем $G$ имеет не более хроматического числа $\gamma$. Лейк (1975) характеризует бесконечные графы, которые подчиняются обобщению теоремы Де Брейна-Эрдёша тем, что их хроматическое число равно максимальному хроматическому числу их строго меньших подграфов.

Ссылки

• Барнетт, Дэвид (1983), Раскраска карт, многогранники и проблема четырех цветов , Dolciani Mathematical Expositions, vol. 8, Математическая ассоциация Америки , с. 160 , ISBN  978-0-88385-309-2 .
• Де Брейн, Северная Каролина ; Эрдеш, П. (1951), «Проблема цвета бесконечных графов и проблема теории отношений» (PDF) , Nederl. Акад. Ветенш. Учеб. Сер. A , 54 : 371–373, doi : 10.1016/S1385-7258(51)50053-7 , MR   0046630 , заархивировано из оригинала (PDF) 10 марта 2016 г. , получено 5 апреля 2010 г.
• Коуэн, Роберт Х. (1990), «Две теоремы о гиперграфах, эквивалентные BPI», Notre Dame Journal of Formal Logic , 31 (2): 232–240, doi : 10.1305/ndjfl/1093635418 , MR   1058424 .
• Коуэн, Роберт; Хеклер, Стивен Х.; Михок, Питер (2002), «Теоремы о компактности раскраски графов, эквивалентные BPI», Japan Mathematical Sciences , 56 (2): 213–223, CiteSeerX   10.1.1.23.1521 , MR   1922784 .
• Эрдеш, П. (1950), «Некоторые замечания по теории множеств» (PDF) , Proceedings of the American Mathematical Society , 1 (2): 127–141, doi : 10.2307/2031913 , JSTOR   2031913 , MR   0035809 .
• Эрдеш, П .; Хайнал, А. (1966), «О хроматическом числе графов и систем множеств» (PDF) , Математический журнал Венгерской академии наук , 17 (1–2): 61–99, doi : 10.1007/BF02020444 , MR   0193025 , S2CID   189780485
• Эрдеш, П .; Хайнал, А. (1968), «О хроматическом числе бесконечных графов», Теория графов (Proc. Colloq., Тихань, 1966) (PDF) , Нью-Йорк: Academic Press, стр. 83–98, MR   0263693 .
• Готшалк, WH (1951), «Функции выбора и теорема Тихонова», Proceedings of the American Mathematical Society , 2 (1): 172, doi : 10.2307/2032641 , JSTOR   2032641 , MR   0040376 .
• Харцхайм, Эгберт (2005), Упорядоченные множества , Успехи в математике, том. 7, Нью-Йорк: Спрингер, Теорема 5.5, с. 59, ISBN  0-387-24219-8 , МР   2127991 .
• Херд, Альберт Э.; Леб, Питер А. (1985), Введение в нестандартный реальный анализ , Чистая и прикладная математика, том. 118, Орландо, Флорида: Academic Press, Теорема 5.14, стр. 118. 92, ISBN  0-12-362440-1 , МР   0806135 .
• Дженсен, Томми Р.; Тофт, Бьерн (1995), Проблемы раскраски графов , Серия Wiley-Interscience по дискретной математике и оптимизации, Нью-Йорк: John Wiley & Sons Inc., Теорема 1, стр. 2–3, ISBN  0-471-02865-7 , МР   1304254 .
• Канамори, Акихиро (2008), Высшая бесконечность: большие кардиналы в теории множеств с самого начала , Монографии Springer по математике (2-е изд.), Springer-Publishers, стр. 37 , ISBN  978-3-540-88866-6 .
• Комьят, Питер (2011), «Хроматическое число бесконечных графов — обзор», Discrete Mathematics , 311 (15): 1448–1450, doi : 10.1016/j.disc.2010.11.004 .
• Лейк, Джон (1975), «Обобщение теоремы де Брюйна и Эрдеша о хроматическом числе бесконечных графов», Журнал комбинаторной теории , серия B, 18 (2): 170–174, doi : 10.1016/0095- 8956(75)90044-1 , МР   0360335 .
• Лэмб, Эвелин (17 апреля 2018 г.), «Задача с графами десятилетней давности поддается математику-любителю» , Quanta Magazine
• Ляухли, Х. (1971), «Раскраска бесконечных графов и булева теорема о простых идеалах», Israel Journal of Mathematics , 9 (4): 422–429, doi : 10.1007/BF02771458 , MR   0288051 .
• Люксембург, W.A.J. (1962), «Замечание к статье Н.Г. де Брейна и П. Эрдеша», Indagationes Mathematicae , 24 : 343–345, doi : 10.1016/S1385-7258(62)50033-4 , МР   0140435 .
• Мисельский, Ян (1961), «Некоторые замечания и проблемы по раскраске бесконечных графов и теореме Куратовского», Acta Mathematica Academiae Scientiarum Hungaricae , 12 (1–2): 125–129, doi : 10.1007/BF02066677 , MR   0130686 , S2CID   120141460 .
• Нэш-Уильямс, К. Ст. Дж. А. (1967), «Бесконечные графы — обзор», Журнал комбинаторной теории , 3 (3): 286–301, doi : 10.1016/s0021-9800(67)80077-2 , MR   0214501 .
• Радо, Р. (1949), «Аксиоматическая трактовка ранга в бесконечных множествах», Canadian Journal of Mathematics , 1 (4): 337–343, doi : 10.4153/cjm-1949-031-1 , S2CID   124598982 .
• Раутенберг, Вольфганг (2010), Краткое введение в математическую логику , Universitext (3-е изд.), Springer-Verlag, стр. 32, номер домена : 10.1007/978-1-4419-1221-3 , ISBN.  978-1-4419-1220-6 .
• Рорабо, Дэнни; Тардиф, Клод; Велау, Дэвид (2017), «Проблемы логической компактности и удовлетворения ограничений», Logical Methods in Computer Science , 13 (1): 1:1–1:11, arXiv : 1609.05221 , doi : 10.23638/LMCS-13(1:1) )2017 , МР   3607036 , S2CID   31135533 .
• Шмерл, Джеймс Х. (2000), «Раскраска графов и обратная математика», Mathematical Logic Quarterly , 46 (4): 543–548, doi : 10.1002/1521-3870(200010)46:4<543::AID-MALQ543 >3.0.CO;2-E , MR   1791549 .
• Шела, Сахарон ; Сойфер, Александр (2003), «Аксиома выбора и хроматическое число плоскости», Журнал комбинаторной теории , серия A, 103 (2): 387–391, doi : 10.1016/S0097-3165(03)00102-X , МР   1996076 .
• Сойфер, Александр (2008), Математическая книжка-раскраска: математика раскраски и красочная жизнь ее создателей , Нью-Йорк: Springer, ISBN  978-0-387-74640-1 . См., в частности, главу II.5 «Сведение Де Брюэна–Эрдёша к конечным множествам и результаты вблизи нижней границы», стр. 39–42, и главу V.26 «Теорема Де Брюэна–Эрдёша и ее история», стр. 236–241. .