12. Некоторые задачи Эрдёша

Несколько задач связано с теорией графов. Они имеют эквивалентные формулировки в нашей терминологии произведения пространств и могут быть поставлены как задачи о подмножествах множества с помощью очевидного соответствия пар точек в концам сегмента в графе. Рассмотрение вершин треугольников в графе может быть заменено рассмотрением соответствующего множества троек из

Некоторые другие задачи принадлежат теории чисел, но имеют комбинаторный характер, и мы включаем их в этот пункт.

1. Пусть множество мощности К. и пусть каждому конечному подмножеству А из отвечает элемент Подмножество называется независимым, если для каждого . У всякого ли множества существует бесконечное независимое подмножество? Если имеет мощность то ответ отрицателен (результат Эрдёша — Хэйнала), но ответ может быть положительным Для К».

2. Задача о бесконечных графах (Эрдёш-Радо). Предположим, что дан бесконечный граф, вершины которого образуют упорядоченное множество типа Если этот граф не содержит треугольника, то существует подмножество

вершин типа никакие две вершины которого не связаны отрезком. Это символически обозначается так: Шпекер (Comm. Helv., 1957) показал, что неверно для Справедливо ли, что

2а. Эрдёш-Радо. Пусть — множество мощности, большей с. Все конечные подмножества произвольным образом разделены на два класса. Существует ли бесконечное подмножество такое, что для любого целого все подмножества имеющие элементов, принадлежат к одному и тому же классу (при этом класс может зависеть от Если мощность 5 с, то ответ отрицателен (Эрдёш — Хэйнал).

3. Пусть полный граф мощности и предположим, что , не содержит полного графа мощности Существует ли треугольник, каждая сторона которого принадлежит различным

Другая задача: полный граф мощности так что не содержит полного графа мощности (такое разложение возможно (Эрдёш-Радо)). Существует ли полный подграф графа мощности все отрезки которого лежат в различных

4. Эрдёш-Туран. Пусть бесконечная последовательность целых чисел. Обозначим через число решений уравнения и предположим, что для Тогда Более определенная постановка задачи: пусть Тогда

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

Как велико может быть Неравенство доказало бы теорему Ван-дер-Вардена, согласно которой при разбиении множества всех целых чисел на две группы по меньшей мере одна из них содержит арифметическую прогрессию со сколь угодно большим числом членов.

(Наилучшие имеющиеся в данное время результаты таковы:

ср. Рот [1] и имеющиеся там ссылки.)

6. Пусть числа выбраны произвольно. Доказать, что для каждого с существуют такие, что Это предположение имеет связь с теоремой Ван-дер-Вардена (см. Хинчин [2]), Отсюда следует также, что если мультипликативна, то

7. Пусть элементов; множества, образованные из этих элементов. Предположим, что никакое не содержит Тогда Это теорема Шпернера [1]. Пусть теперь множества, образованные из элементов а, так, что никакое не есть сумма двух других множеств отличных от него самого? Каково максимально возможное 11 Вполне возможно, что Эрдёш утверждает, что он не может даже доказать, что

8. Пусть Рассмотрим все суммы вида

Эрдёш доказывает, используя вышеприведенный результат Шпернера (и уточняя уже имевшийся результат Литлвуда и Оффорда), что число этих сумм, попадающих внутрь интервала длины 2, не превосходит Равенство имеет место для Справедливо ли предположение, что

этот же результат имеет место, если комплексные числа по модулю 1 и интервал заменен кругом радиуса 1. Тот же результат может иметь место, если векторы в гильбертовом (банаховом) пространстве.

9. Пусть две такие последовательности целых чисел, что все произведения различны. Доказать, что

Если это верно, то это наилучший возможный результат.

10. Сколько различных вычетов можно указать так, чтобы никакие из сумм не были Очевидно, можно указать [2] таких вычетов Хорошая верхняя граница неизвестна.

11. Эрдёш и автор. Пусть - произвольный конечноаддитивный идеал в множестве целых чисел. Рассмотрим булеву алгебру подмножеств множества целых чисел Можно ли таким способом получить неизоморфных булевых алгебр?