Полные графы в R^n

[Профессор Снэйп]

Не помню, формулировал ли уже здесь эту задачу. Поискал - не нашёл...

Пусть $A \subseteq \mathbb{R}^n$ и для любых различных $x_1, x_2, x_3, x_4 \in A$ отрезки $[x_1, x_2]$ и $[x_3, x_4]$ не пересекаются. Какова максимально возможная мощность множества $A$?

Другими словами, насколько большой полный граф можно корректно нарисовать в $\mathbb{R}^n$?

[Padawan]

Профессор Снэйп
При $n\geqslant 3$ сколь угодно большой (но конечный).

[Профессор Снэйп]

Padawan в сообщении #567933 писал(а):

Профессор Снэйп
При $n\geqslant 3$ сколь угодно большой (но конечный).

Это неправильный ответ.

-- Вс май 06, 2012 17:12:05 --

На самом деле я сейчас, пока мылся в ванне, понял, что формулировка не совсем корректна. В частности, при $n = 1$ она предполагает ответ $3$, хотя на самом деле полный граф с тремя вершинами в $\mathbb{R}$ не вкладывается (а вкладывается лишь полный граф с двумя вершинами)...

Но при $n = 0$ и $n \geqslant 2$ вроде всё корректно. Сейчас подумаю, как лучше переформулировать...

-- Вс май 06, 2012 17:17:16 --

Формулировка номер 2: Множество $A \subseteq \mathbb{R}^n$ называется изображением полного графа, если для любых $x_1, x_2, x_3, x_4 \in A$ справедливо $[x_1, x_2] \cap [x_3, x_4] = \{ x_1, x_2 \} \cap \{ x_3, x_4 \}$. Какова максимальная мощность изображения полного графа?

-- Вс май 06, 2012 17:18:53 --

Чёрт, опять ерунда! Сейчас ещё подумаю...

[Padawan]

Профессор Снэйп в сообщении #567938 писал(а):

Padawan в сообщении #567933 писал(а):

Профессор Снэйп
При $n\geqslant 3$ сколь угодно большой (но конечный).

Это неправильный ответ.

Не может быть. Для любого $m\in\mathbb N$ в $\mathbb R^3$ найдется $m$ точек, никакие четыре из которых не лежат в одной плоскости. Соединяя их попарно отрезками, получим нужный граф.

[Профессор Снэйп]

А если так?

Формулировка номер 3: Множество $A \subseteq \mathbb{R}^n$ называется изображением полного графа, если для любых $x_1, x_2, x_3, x_4 \in A$, таких что $[x_1, x_2] \neq [x_3, x_4]$, справедливо $[x_1, x_2] \cap [x_3, x_4] = \{ x_1, x_2 \} \cap \{ x_3, x_4 \}$. Какова максимальная мощность изображения полного графа?

Вроде пока косяков не вижу. Но даже если они есть (кстати, буду благодарен, если кто-нибудь на них укажет), то... Я думаю, смысл задачи все поняли. Граф корректно нарисован в $\mathbb{R}^n$, если рёбра не пересекаются так, что на изображении появляются лишние вершины, создаваемые пересечениями рёбер (которые рисуются как отрезки). Ну и насколько большой полный граф можно нарисовать в $\mathbb{R}^n$?

-- Вс май 06, 2012 17:32:07 --

Padawan в сообщении #567949 писал(а):

Профессор Снэйп в сообщении #567938 писал(а):

Padawan в сообщении #567933 писал(а):

Профессор Снэйп
При $n\geqslant 3$ сколь угодно большой (но конечный).

Это неправильный ответ.

Не может быть. Для любого $m\in\mathbb N$ в $\mathbb R^3$ найдется $m$ точек, никакие четыре из которых не лежат в одной плоскости. Соединяя их попарно отрезками, получим нужный граф.

Я понял Ваш ответ так, что при $n \geqslant 3$ сколь угодно большой конечный полный граф в $\mathbb{R}^n$ нарисовать можно, а бесконечный уже нельзя. С этим я несогласен, можно нарисовать и бесконечный!

[Padawan]

Профессор Снэйп
Про бесконечный я ничего не утверждал. Просто плохо выразился, извиняюсь. Сейчас про бесконечный подумаю. А ну да, по одной точке добавлять так, чтобы на каждом шаге никакие четыре не лежали в одной плоскости. И потом взять объединение всех этих точек. То есть счетное можно. А больше счетного?

[Профессор Снэйп]

Padawan в сообщении #567953 писал(а):

А больше счетного?

В этом и состоит вопрос задачи, ответ на который предлагается найти

[Padawan]

Вроде можно в $\mathbb R^3$ построить множество типа канторова, никакие четыре точки которого не лежат в одной плоскости. На шаге 1 берем тетраэдр и вокруг каждой вершины проводим сферу столь малого радиуса, чтобы никакие четыре точки, взятые внутри этих сфер (в каждой сфере по точке) не лежали в одной плоскости. На шаге 2 внутри каждой сферы строим по тетраэдру так, чтобы никакие из 16 полученных точек не лежали в одной плоскости, вокруг каждой точки проводим сферу. И т.д.

Короче, континуум можно.

[Профессор Снэйп]

Что-то я не понял этого решения

Вот мы для каждого $t \in \mathbb{N}$ на шаге $t$ добавили конечное количество точек. В итоге получили счётное множество точек! Или там как-то сложнее?

[Padawan]

Профессор Снэйп
Нет, строим канторово множество. Точка этого множества задается последовательностью шаров, выбираемых на каждом шаге, в виде их пересечения.

[Профессор Снэйп]

А-а-а, понял!... У Вас не сферы, а шары, на каждом шаге внутри каждого шара делаем четыре маленьких шара, а требуется множество предельных точек всех возможных последовательностей вложенных шаров. Таких предельных точек, конечно же, континуум!

-- Вс май 06, 2012 18:12:06 --

Padawan в сообщении #567962 писал(а):

Точка этого множества задается последовательностью шаров...

Ага, вот Вы и сами написали про шары. А сначала писали про сферы, меня это сбило с толку.

[Padawan]

Профессор Снэйп
Вокруг точки строим шар как-то не звучит :)

[Профессор Снэйп]

(Афтарское решение)

В $\mathbb{R}^3$ достаточно рассмотреть $A = \{ (t,t^2,t^3) : t \in \mathbb{R} \}$. Теперь надо доказать, что никакие четыре различных точки из $A$ не лежат в одной плоскости. Простыми алгебраическими выкладками всё сводится к определителю Вандермонда.

-- Вс май 06, 2012 18:15:20 --

Padawan в сообщении #567965 писал(а):

Вокруг точки строим шар как-то не звучит :)

Строим шар с центром в данной точке

[Padawan]

(Оффтоп)

Профессор Снэйп
Ваше решение лучше.

[Профессор Снэйп]

Padawan в сообщении #567967 писал(а):

Ваше решение лучше.

На самом деле оно не моё, а одного из участников форума НГУ, известного под ником В.П. Вот ссылка.

Там, кстати, есть и третье решение, по трансфинитной индукции. Вот оно уже моё...