The De Bruijn-Erdős theorem also applies directly to hypergraph coloring problems, where one requires that each hyperedge have vertices of more than one color. |
Теорема де Брёйна - Эрдёша также применима прямо к задачам раскраски гиперграфов, где требуется, чтобы каждое гиперребро имело вершины более одного цвета. |
The original De Bruijn-Erdős theorem is the case k = ℵ0 of this generalization, since a set is finite if and only if its cardinality is less than ℵ0. |
Оригинальная теорема де Брёйна - Эрдёша является частным случаем к = ℵ0 этого обобщения, поскольку множество конечно тогда и только тогда, когда его мощность меньше ℵ0. |
The De Bruijn-Erdős theorem shows that, for this problem, there exists a finite unit distance graph with the same chromatic number as the whole plane, so if the chromatic number is greater than five then this fact can be proved by a finite calculation. |
Теорема де Брёйна - Эрдёша показывает, что для этой задачи существует конечный граф единичных расстояний с тем же хроматическим числом, что и вся плоскость целиком, так что если хроматическое число больше четырёх, то этот факт может быть доказан конечными вычислениями. |
Elekes and Csaba Toth noted that the Erdős-Beck theorem does not easily extend to higher dimensions. |
Элекеш и Чаба Тоз заметили, что теорема Эрдёша - Бека не распространяется легко на более высокие размерности. |
If a graph does not have finite chromatic number, then the De Bruijn-Erdős theorem implies that it must contain finite subgraphs of every possible finite chromatic number. |
Если граф не имеет конечного хроматического числа, тогда из теоремы де Брёйна - Эрдёша следует, что граф должен содержать конечные подграфы для каждого возможного хроматического числа. |
G is finite (this is the de Bruijn-Erdős theorem of de Bruijn & Erdős 1951). δ(G) >= k - 1, that is, every vertex is adjacent to at least k - 1 others. |
G конечен (теорема де Брёйна - Эрдёша). δ(G) >= k - 1, то есть любая вершина смежна по меньшей мере k - 1 другим вершинам. |
Instead of cliques, if the same question is asked for complete multi-partite graphs, the answer is given by the Erdős-Stone theorem. |
Если вместо клик в аналогичном вопросе спрашиваются о полных многодольных графах, ответ даёт теорема Эрдёша - Стоуна. |
Ramsey's theorem also implies the special case of the Erdős-Hajnal conjecture when H {\displaystyle H} itself is a clique or independent set. |
Из теоремы Рамсея также следует специальный случай гипотезы Эрдёша - Хайналя, когда сам граф Н {\displaystyle H} является кликой или независимым множеством. |
The De Bruijn-Erdős theorem may also be used to extend Dilworth's theorem from finite to infinite partially ordered sets. |
Теорема де Брёйна - Эрдёша может быть использована также для расширения теоремы Дилуорса от конечного варианта к бесконечным частично упорядоченным множествам. |
The Erdős-Szekeres theorem on monotone subsequences can be interpreted as an application of Dilworth's theorem to partial orders of order dimension two (Steele 1995). |
Теорему Эрдёша - Секереша о монотонных подпоследовательностях можно интерпретировать как приложение теоремы Дилуорса к частичным порядкам размерности два (Steele 1995). |
Gottschalk states his proof more generally as a proof of the theorem of Rado (1949) that generalizes the De Bruijn-Erdős theorem. |
Готтшальк утверждает, что его доказательство более обще, чем доказательство теоремы Радо (Rado 1949), которая обобщает теорему де Брёйна - Эрдёша. |
For this connection between Rado's lemma and the De Bruijn-Erdős theorem, see e.g. the discussion following Theorem A of Nash-Williams (1967). |
Для связи леммы Радо и теоремы де Брёйна - Эрдёша см. обсуждение после теоремы А у Нэша-Вилльямса (Nash-Williams 1967). |
Beck's Theorem can be derived by letting k = n(1 - 1/C) and applying the Erdős-Beck theorem. |
Теорема Бека получается, если положить к = n(1 - 1/C) и применить теорему Эрдёша - Бека. |
Its applications include extending the four-color theorem and Dilworth's theorem from finite graphs and partially ordered sets to infinite ones, and reducing the Hadwiger-Nelson problem on the chromatic number of the plane to a problem about finite graphs. |
Теорема применяется для расширения задачи четырёх красок и теоремы Дилуорса для конечных графов и множеств с частичным порядком до бесконечных вариантов, сведения задачи Нельсона - Эрдёша - Хадвигера о хроматическом числе плоскости к задачам на конечных графах. |