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

О раскраске бесконечных графов

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

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

Определения и утверждения

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

Подграф графа — это другой граф, полученный из подмножества его вершин и подмножества его ребер. Если больший граф раскрашен, то для подграфа может быть использована та же раскраска. Следовательно, хроматическое число подграфа не может быть больше хроматического числа всего графа. Теорема де Брейна–Эрдёша касается хроматических чисел бесконечных графов и показывает, что (опять же, предполагая аксиому выбора) их можно вычислить из хроматических чисел их конечных подграфов. Она утверждает, что если хроматические числа конечных подграфов графа имеют конечное максимальное значение , то хроматическое число самого графа равно в точности . С другой стороны, если нет конечной верхней границы хроматических чисел конечных подграфов графа , то хроматическое число самого графа должно быть бесконечным. ^[4] ${\displaystyle G}$ ${\displaystyle c}$ ${\displaystyle G}$ ${\displaystyle c}$ ${\displaystyle G}$ ${\displaystyle G}$

Приложения

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

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

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

Теорема Де Брейна–Эрдёша может также использоваться для расширения теоремы Дилворта с конечных на бесконечные частично упорядоченные множества . Теорема Дилворта утверждает, что ширина частичного порядка (максимальное число элементов в наборе взаимно несравнимых элементов) равна минимальному числу цепей ( полностью упорядоченных подмножеств), на которые может быть разбит частичный порядок. Разбиение на цепи может быть интерпретировано как раскраска графа несравнимости частичного порядка. Это граф с вершиной для каждого элемента порядка и ребром для каждой пары несравнимых элементов. Используя эту интерпретацию раскраски вместе с отдельным доказательством теоремы Дилворта для конечных частично упорядоченных множеств, можно доказать, что бесконечное частично упорядоченное множество имеет конечную ширину тогда и только тогда, когда оно имеет разбиение на цепи. ^[8] ${\displaystyle w}$ ${\displaystyle w}$

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

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

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

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

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

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

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

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

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

Обобщения

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

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

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

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

Примечания

1. Для этих основных определений см. Jensen & Toft (1995), стр. 1–2.
2. Дженсен и Тофт (1995), стр. 5.
3. Комьят (2011).
4. Дженсен и Тофт (1995), Теорема 1, стр. 2.
5. Эрдёш (1950). См. в частности стр. 137, где теорема Де Брейна–Эрдёша впервые анонсирована (но не доказана) с намеком на то, что лемму Кёнига можно использовать для счётных графов.
6. Лэмб (2018).
7. Сойфер (2008), стр. 39.
8. Харцхейм (2005), Теорема 5.6, стр. 60.
9. Barnette (1983). Нэш-Вильямс (1967) утверждает тот же результат для теоремы о пяти цветах для счетных планарных графов, поскольку теорема о четырех цветах еще не была доказана, когда он опубликовал свой обзор, и поскольку доказательство теоремы Де Брейна–Эрдёша, которое он дает, применимо только к счетным графам. Обобщение на графы, в которых каждый конечный подграф является планарным (доказано непосредственно с помощью теоремы Гёделя о компактности), см. в Rautenberg (2010).
10. Сойфер (2008), стр. 236.
11. Йенсен и Тофт (1995). Готтшалк формулирует свое доказательство в более общем виде как доказательство теоремы Радо (1949), которая обобщает теорему Де Брейна–Эрдёша.
12. Йенсен и Тофт (1995); Харцхайм (2005). Йенсен и Тофт приписывают Герту Сабидусси наблюдение, что доказательство Готтшалка легче обобщить. Сойфер (2008, стр. 238–239) приводит то же доказательство с помощью леммы Цорна, заново открытой в 2005 году студентом бакалавриата Дмитрием Карабашем.
13. Люксембург (1962).
14. Херд и Лоэб (1985).
15. Для этой истории см. Cowen, Hechler & Mihók (2002). Для упрощенного доказательства теоремы Лойхли, сделанного Mycielski, см. Cowen (1990).
16. Шмерль (2000).
17. Шела и Сойфер (2003); Сойфер (2008), стр. 541–542.
18. О связи между леммой Радо и теоремой де Брейна–Эрдёша см., например, обсуждение после теоремы А Нэша-Вильямса (1967).
19. Эрдеш и Хайнал (1966); Комьят (2011).
20. Сойфер (2008), стр. 239.
21. Лейк (1975), стр. 171: «Доказать [теорему Де Брейна–Эрдёша] легко, используя теорему о компактности для логики первого порядка»
22. Рорабо, Тардиф и Велау (2017).
23. Это следует непосредственно из определения сильно компактного кардинала как кардинала, такого, что любая совокупность формул бесконечной логики, каждая из которых имеет длину меньше , которая выполнима для любой подсовокупности из меньшего числа формул, является глобально выполнимой. См., например, Kanamori (2008). ${\displaystyle \kappa }$ ${\displaystyle \kappa }$ ${\displaystyle \kappa }$
24. Эрдёш и Хайнал (1968).

Ссылки

• Барнетт, Дэвид (1983), Раскраска карт, многогранники и проблема четырех цветов, Dolciani Mathematical Expositions, т. 8, Математическая ассоциация Америки , стр. 160, ISBN 978-0-88385-309-2.
• De Bruijn, NG ; Erdős, P. (1951), "Проблема цвета для бесконечных графов и проблема в теории отношений" (PDF) , Nederl. Akad. Wetensch. Proc. Ser. A , 54 : 371–373, doi :10.1016/S1385-7258(51)50053-7, MR  0046630, архивировано из оригинала (PDF) 2016-03-10 , извлечено 2010-04-05.
• Коуэн, Роберт Х. (1990), «Две теоремы о гиперграфах, эквивалентные BPI», Notre Dame Journal of Formal Logic , 31 (2): 232–240, doi : 10.1305/ndjfl/1093635418 , MR  1058424.
• Коуэн, Роберт; Хеклер, Стивен Х.; Михок, Питер (2002), «Теоремы о компактности раскраски графов, эквивалентные BPI», Scientiae Mathematicae Japonicae , 56 (2): 213–223, CiteSeerX  10.1.1.23.1521 , MR  1922784.
• Эрдёш, П. (1950), «Некоторые замечания по теории множеств» (PDF) , Труды Американского математического общества , 1 (2): 127–141, doi :10.2307/2031913, JSTOR  2031913, MR  0035809.
• Эрдеш, П .; Хайнал, А. (1966), «О хроматическом числе графов и систем множеств» (PDF) , Acta Mathematica Academiae Scientiarum Hungaricae , 17 (1–2): 61–99, doi : 10.1007/BF02020444, MR  0193025, S2CID  189780485.
• Эрдёш, П.; Хайнал , А. (1968), «О хроматическом числе бесконечных графов», Теория графов (Proc. Colloq., Тихань, 1966) (PDF) , Нью-Йорк: Academic Press, стр. 83–98, MR  0263693.
• Gottschalk, WH (1951), "Функции выбора и теорема Тихонова", Труды Американского математического общества , 2 (1): 172, doi :10.2307/2032641, JSTOR  2032641, MR  0040376.
• Харцхейм, Эгберт (2005), Упорядоченные множества, Advances in Mathematics, т. 7, Нью-Йорк: Springer, Теорема 5.5, стр. 59, ISBN 0-387-24219-8, МР  2127991.
• Херд, Альберт Э.; Лёб, Питер А. (1985), Введение в нестандартный вещественный анализ, Чистая и прикладная математика, т. 118, Орландо, Флорида: Academic Press, Теорема 5.14, стр. 92, ISBN 0-12-362440-1, МР  0806135.
• Дженсен, Томми Р.; Тофт, Бьярне (1995), Проблемы раскраски графов , Wiley-Interscience Series in Discrete Mathematics and Optimization, Нью-Йорк: John Wiley & Sons Inc., Теорема 1, стр. 2–3, ISBN 0-471-02865-7, МР  1304254.
• Канамори, Акихиро (2008), Высшая бесконечность: большие кардиналы в теории множеств с самого начала , Монографии Springer по математике (2-е изд.), Springer-Verlag, стр. 37, ISBN 978-3-540-88866-6.
• Комят, Петер (2011), «Хроматическое число бесконечных графов — обзор», Дискретная математика , 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 , MR  0360335.
• Лэмб, Эвелин (17 апреля 2018 г.), «Десятилетняя задача о графах поддается решению математиков-любителей», Quanta Magazine
• Лёйхли, Х. (1971), «Раскраска бесконечных графов и теорема о простом идеале Буля», Israel Journal of Mathematics , 9 (4): 422–429, doi :10.1007/BF02771458, MR  0288051.
• Люксембург, WAJ (1962), «Замечание к статье Н.Г. де Брейна и П. Эрдеша», Indagationes Mathematicae , 24 : 343–345, doi : 10.1016/S1385-7258(62)50033-4 , MR  0140435.
• Мисельский, Ян (1961), «Некоторые замечания и проблемы по раскраске бесконечных графов и теореме Куратовского», Acta Mathematica Academiae Scientiarum Hungaricae , 12 (1–2): 125–129, doi : 10.1007/BF02066677, MR  0130686 , S2CID  120141460.
• Нэш-Уильямс, К. Ст. JA (1967), «Бесконечные графы — обзор», Журнал комбинаторной теории , 3 (3): 286–301, doi : 10.1016/s0021-9800(67)80077-2 , MR  0214501.
• Радо, Р. (1949), «Аксиоматическая трактовка ранга в бесконечных множествах», Канадский журнал математики , 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), «Логическая компактность и проблемы удовлетворения ограничений», Логические методы в информатике , 13 (1): 1:1–1:11, arXiv : 1609.05221 , doi : 10.23638/LMCS-13(1:1)2017, MR  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, MR  1996076.
• Сойфер, Александр (2008), Математическая раскраска: математика раскрашивания и красочная жизнь ее создателей , Нью-Йорк: Springer, ISBN 978-0-387-74640-1. См. особенно главу II.5 «Редукция Де Брюина–Эрдёша к конечным множествам и результаты вблизи нижней границы», стр. 39–42, и главу V.26 «Теорема Де Брюина–Эрдёша и ее история», стр. 236–241.