Задачи в теории Рамсея обычно звучат в форме вопроса «сколько элементов должно быть в некотором объекте, чтобы гарантированно выполнялось заданное условие или существовала заданная структура».
Простейший пример: доказать, что в любой группе из 6 человек найдутся либо 3 человека, попарно знакомые друг с другом, либо 3 человека, попарно незнакомые друг с другом.
Для доказательства возьмём любого из шестерых — назовём его А. Предположим, что он знает хотя бы троих из оставшихся. Если среди этих троих есть двое знакомых, они образуют искомую тройку (попарно знакомых) с А, если нет — то тройку попарно незнакомых между собой. Если же А знает не более двоих из оставшихся, то у него есть трое незнакомых, и для них работает аналогичное рассуждение. Также легко видеть, что в компании из пяти человек может уже не найтись троих попарно знакомых или попарно незнакомых: поставим пятерых изначально незнакомых людей по кругу и познакомим соседей.
На языке теории графов это утверждение формулируется так: если есть граф с шестью вершинами (это люди), ребра которого раскрашены в красный и синий цвета (знакомство и незнакомство соответственно), то найдутся три вершины, соединённые рёбрами одного цвета. А для графа с пятью вершинами такой тройки может и не быть.
А если мы хотим найти в какой-нибудь группе больше людей, которые или каждый с каждым знакомы, или каждый с каждым не знакомы? Верно ли, что какие бы значения n и k мы не взяли, в достаточно большой компании найдутся или n попарно знакомых, или k попарно незнакомых людей? Да, верно: это утверждает теорема Рамсея, доказанная им в 1930 г. Наименьший размер компании, заведомо удовлетворяющей этому условию, обозначается R(n, k) и называется числом Рамсея. Или, учитывая синюю группу из n вершин или красную группу из k вершин, минимальное количество вершин, которое должен иметь полный граф, чтобы каждое ребро было окрашено в красный или синий цвет.
Выше мы установили, что R(3,3) = 6. Считать числа Рамсея очень трудно. Известно, что, например, R(4,4) = 18 — соответствующий граф показан на рисунке.
R(4,5) = 25 (это сложно). А R(5,5) никто не знает, известно только, что 43 ⩽ R(5,5) ⩽ 48.
Фактически теорема Рамсея утверждает, что любая структура обязательно содержит упорядоченную подструктуру, а полный беспорядок невозможен. Если число объектов (звёзд, камней, людей, геометрических точек и т.п.) в совокупности достаточно велико и любые два объекта связывает одно из набора отношений, то всегда существует подмножество данной совокупности, содержащее заданное число объектов, и при этом такое, что в нём все объекты связаны отношением одного типа.
Теория Рамсея возникла как обобщение принципа Дирихле. Для её результатов характерна неконструктивность: доказывается, что некоторая структура существует, но не предлагается никакого способа её построения кроме прямого перебора. Кроме того, для существования искомых структур требуется, чтобы объекты, их содержащие, состояли из очень большого числа элементов. Зависимость числа элементов объекта от размера структуры обычно, как минимум, экспоненциальная.
Теория Рамсея имеет много интересных приложений, включая результаты в области теории чисел, геометрии, алгебры, топологии, логики, теории множеств, эргодической теории, теоретической информатики и теории информации.
Простейший пример: доказать, что в любой группе из 6 человек найдутся либо 3 человека, попарно знакомые друг с другом, либо 3 человека, попарно незнакомые друг с другом.
Для доказательства возьмём любого из шестерых — назовём его А. Предположим, что он знает хотя бы троих из оставшихся. Если среди этих троих есть двое знакомых, они образуют искомую тройку (попарно знакомых) с А, если нет — то тройку попарно незнакомых между собой. Если же А знает не более двоих из оставшихся, то у него есть трое незнакомых, и для них работает аналогичное рассуждение. Также легко видеть, что в компании из пяти человек может уже не найтись троих попарно знакомых или попарно незнакомых: поставим пятерых изначально незнакомых людей по кругу и познакомим соседей.
На языке теории графов это утверждение формулируется так: если есть граф с шестью вершинами (это люди), ребра которого раскрашены в красный и синий цвета (знакомство и незнакомство соответственно), то найдутся три вершины, соединённые рёбрами одного цвета. А для графа с пятью вершинами такой тройки может и не быть.
А если мы хотим найти в какой-нибудь группе больше людей, которые или каждый с каждым знакомы, или каждый с каждым не знакомы? Верно ли, что какие бы значения n и k мы не взяли, в достаточно большой компании найдутся или n попарно знакомых, или k попарно незнакомых людей? Да, верно: это утверждает теорема Рамсея, доказанная им в 1930 г. Наименьший размер компании, заведомо удовлетворяющей этому условию, обозначается R(n, k) и называется числом Рамсея. Или, учитывая синюю группу из n вершин или красную группу из k вершин, минимальное количество вершин, которое должен иметь полный граф, чтобы каждое ребро было окрашено в красный или синий цвет.
Выше мы установили, что R(3,3) = 6. Считать числа Рамсея очень трудно. Известно, что, например, R(4,4) = 18 — соответствующий граф показан на рисунке.
R(4,5) = 25 (это сложно). А R(5,5) никто не знает, известно только, что 43 ⩽ R(5,5) ⩽ 48.
Фактически теорема Рамсея утверждает, что любая структура обязательно содержит упорядоченную подструктуру, а полный беспорядок невозможен. Если число объектов (звёзд, камней, людей, геометрических точек и т.п.) в совокупности достаточно велико и любые два объекта связывает одно из набора отношений, то всегда существует подмножество данной совокупности, содержащее заданное число объектов, и при этом такое, что в нём все объекты связаны отношением одного типа.
Теория Рамсея возникла как обобщение принципа Дирихле. Для её результатов характерна неконструктивность: доказывается, что некоторая структура существует, но не предлагается никакого способа её построения кроме прямого перебора. Кроме того, для существования искомых структур требуется, чтобы объекты, их содержащие, состояли из очень большого числа элементов. Зависимость числа элементов объекта от размера структуры обычно, как минимум, экспоненциальная.
Теория Рамсея имеет много интересных приложений, включая результаты в области теории чисел, геометрии, алгебры, топологии, логики, теории множеств, эргодической теории, теоретической информатики и теории информации.
group-telegram.com/math_essence/819
Create:
Last Update:
Last Update:
Задачи в теории Рамсея обычно звучат в форме вопроса «сколько элементов должно быть в некотором объекте, чтобы гарантированно выполнялось заданное условие или существовала заданная структура».
Простейший пример: доказать, что в любой группе из 6 человек найдутся либо 3 человека, попарно знакомые друг с другом, либо 3 человека, попарно незнакомые друг с другом.
Для доказательства возьмём любого из шестерых — назовём его А. Предположим, что он знает хотя бы троих из оставшихся. Если среди этих троих есть двое знакомых, они образуют искомую тройку (попарно знакомых) с А, если нет — то тройку попарно незнакомых между собой. Если же А знает не более двоих из оставшихся, то у него есть трое незнакомых, и для них работает аналогичное рассуждение. Также легко видеть, что в компании из пяти человек может уже не найтись троих попарно знакомых или попарно незнакомых: поставим пятерых изначально незнакомых людей по кругу и познакомим соседей.
На языке теории графов это утверждение формулируется так: если есть граф с шестью вершинами (это люди), ребра которого раскрашены в красный и синий цвета (знакомство и незнакомство соответственно), то найдутся три вершины, соединённые рёбрами одного цвета. А для графа с пятью вершинами такой тройки может и не быть.
А если мы хотим найти в какой-нибудь группе больше людей, которые или каждый с каждым знакомы, или каждый с каждым не знакомы? Верно ли, что какие бы значения n и k мы не взяли, в достаточно большой компании найдутся или n попарно знакомых, или k попарно незнакомых людей? Да, верно: это утверждает теорема Рамсея, доказанная им в 1930 г. Наименьший размер компании, заведомо удовлетворяющей этому условию, обозначается R(n, k) и называется числом Рамсея. Или, учитывая синюю группу из n вершин или красную группу из k вершин, минимальное количество вершин, которое должен иметь полный граф, чтобы каждое ребро было окрашено в красный или синий цвет.
Выше мы установили, что R(3,3) = 6. Считать числа Рамсея очень трудно. Известно, что, например, R(4,4) = 18 — соответствующий граф показан на рисунке.
R(4,5) = 25 (это сложно). А R(5,5) никто не знает, известно только, что 43 ⩽ R(5,5) ⩽ 48.
Фактически теорема Рамсея утверждает, что любая структура обязательно содержит упорядоченную подструктуру, а полный беспорядок невозможен. Если число объектов (звёзд, камней, людей, геометрических точек и т.п.) в совокупности достаточно велико и любые два объекта связывает одно из набора отношений, то всегда существует подмножество данной совокупности, содержащее заданное число объектов, и при этом такое, что в нём все объекты связаны отношением одного типа.
Теория Рамсея возникла как обобщение принципа Дирихле. Для её результатов характерна неконструктивность: доказывается, что некоторая структура существует, но не предлагается никакого способа её построения кроме прямого перебора. Кроме того, для существования искомых структур требуется, чтобы объекты, их содержащие, состояли из очень большого числа элементов. Зависимость числа элементов объекта от размера структуры обычно, как минимум, экспоненциальная.
Теория Рамсея имеет много интересных приложений, включая результаты в области теории чисел, геометрии, алгебры, топологии, логики, теории множеств, эргодической теории, теоретической информатики и теории информации.
Простейший пример: доказать, что в любой группе из 6 человек найдутся либо 3 человека, попарно знакомые друг с другом, либо 3 человека, попарно незнакомые друг с другом.
Для доказательства возьмём любого из шестерых — назовём его А. Предположим, что он знает хотя бы троих из оставшихся. Если среди этих троих есть двое знакомых, они образуют искомую тройку (попарно знакомых) с А, если нет — то тройку попарно незнакомых между собой. Если же А знает не более двоих из оставшихся, то у него есть трое незнакомых, и для них работает аналогичное рассуждение. Также легко видеть, что в компании из пяти человек может уже не найтись троих попарно знакомых или попарно незнакомых: поставим пятерых изначально незнакомых людей по кругу и познакомим соседей.
На языке теории графов это утверждение формулируется так: если есть граф с шестью вершинами (это люди), ребра которого раскрашены в красный и синий цвета (знакомство и незнакомство соответственно), то найдутся три вершины, соединённые рёбрами одного цвета. А для графа с пятью вершинами такой тройки может и не быть.
А если мы хотим найти в какой-нибудь группе больше людей, которые или каждый с каждым знакомы, или каждый с каждым не знакомы? Верно ли, что какие бы значения n и k мы не взяли, в достаточно большой компании найдутся или n попарно знакомых, или k попарно незнакомых людей? Да, верно: это утверждает теорема Рамсея, доказанная им в 1930 г. Наименьший размер компании, заведомо удовлетворяющей этому условию, обозначается R(n, k) и называется числом Рамсея. Или, учитывая синюю группу из n вершин или красную группу из k вершин, минимальное количество вершин, которое должен иметь полный граф, чтобы каждое ребро было окрашено в красный или синий цвет.
Выше мы установили, что R(3,3) = 6. Считать числа Рамсея очень трудно. Известно, что, например, R(4,4) = 18 — соответствующий граф показан на рисунке.
R(4,5) = 25 (это сложно). А R(5,5) никто не знает, известно только, что 43 ⩽ R(5,5) ⩽ 48.
Фактически теорема Рамсея утверждает, что любая структура обязательно содержит упорядоченную подструктуру, а полный беспорядок невозможен. Если число объектов (звёзд, камней, людей, геометрических точек и т.п.) в совокупности достаточно велико и любые два объекта связывает одно из набора отношений, то всегда существует подмножество данной совокупности, содержащее заданное число объектов, и при этом такое, что в нём все объекты связаны отношением одного типа.
Теория Рамсея возникла как обобщение принципа Дирихле. Для её результатов характерна неконструктивность: доказывается, что некоторая структура существует, но не предлагается никакого способа её построения кроме прямого перебора. Кроме того, для существования искомых структур требуется, чтобы объекты, их содержащие, состояли из очень большого числа элементов. Зависимость числа элементов объекта от размера структуры обычно, как минимум, экспоненциальная.
Теория Рамсея имеет много интересных приложений, включая результаты в области теории чисел, геометрии, алгебры, топологии, логики, теории множеств, эргодической теории, теоретической информатики и теории информации.
BY Математическая эссенция
Share with your friend now:
group-telegram.com/math_essence/819