Суперграфы в R^n

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

Суперграфом будем называть пару $\langle V, R \rangle$, где $V$ --- произвольное множество, а $R$ --- семейство трёхэлементных подмножеств $V$ (по аналогии с графами, неориентированный граф можно определить как пару $\langle U, S \rangle$, где $U$ --- множество вершин, а $S$ --- семейство двухэлементных подмножеств $U$, состоящее из пар различных вершин, соединённых ребром).

Для суперграфа $\langle V, R \rangle$ множество $V$ будем называть множеством вершин этого суперграфа, а $R$ --- множеством рёбер. Под мощностью суперграфа будем понимать мощность множества его вершин.

Скажем, что суперграф $\langle V, R \rangle$ является полным, если $R$ совпадает с множеством всех трёхэлементных подмножеств $V$ (то есть если любые 3 различных вершины этого суперграфа соединены ребром).

Скажем, что суперграф $\langle V, R \rangle$ вложен в $\mathbb{R}^n$, если $V \subseteq \mathbb{R}^n$ и для любых $\{ x_1, y_1, z_1\}, \{ x_2, y_2, z_2 \} \in R$ пересечение выпуклых оболочек этих множеств совпадает с выпуклой оболочкой их пересечения.

1) Доказать, что максимальная мощность полного суперграфа, вложенного в $\mathbb{R}^3$, равна $5$.

2) Доказать, что в $\mathbb{R}^5$ можно вложить континуальный полный суперграф.

3) Выяснить, чему равна максимальная мощность полного суперграфа, вложенного в $\mathbb{R}^4$.

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

Может, стоило начать с обычных графов?

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

1) Доказать, что максимальная мощность полного графа, вложенного в $\mathbb{R}^2$, равна 4.

2) Доказать, что в $\mathbb{R}^3$ можно вложить полный граф, имеющий континуум вершин.

[Kid Kool]

Хе, ну 1) -то совсем просто: 4 вершины - это только треугольник с еще одной вершиной внутри него (и никак иначе), а пятую вершину приткнуть не получится ни в одну из 4-х образовавшихся областей.

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

Kid Kool писал(а):

Хе, ну 1) -то совсем просто: 4 вершины - это только треугольник с еще одной вершиной внутри него (и никак иначе), а пятую вершину приткнуть не получится ни в одну из 4-х образовавшихся областей.

Не уверен, что такую "наглядную картинку" можно рассматривать как строгое доказательство. Но в принципе понятно, что оно так и есть.

В первоначальной задаче про суперграфы первый номер столь же прост. Пять вершин --- это тетраэдр с одной вершиной внутри

[Kid Kool]

2) Покажем что к любому полному графу конечной мощности, вложенному в $\mathbb{R}^3$, можно добавить еще вершину с любой наперед заданной аппликатой (3-ей координатой), отличной от аппликат всех вершин графа - с сохранением вложенности графа в $\mathbb{R}^3$.

Действительно, добавили вершину x. Допустим что, образовались какие-то пересечения с ребрами графа, рассмотрим одно из них. Пусть минимальное из ненулевых расстояний между всеми ребрами равно $\epsilon$. Подвинем вершину x в плоскости, параллельной XY на расстояние $\frac{\epsilon}{2}$, в итоге рассматриваемое пересечение ребер исчезнет, а новых не появится. Так изведем все пересечения.

А теперь просто к пустому множеству вершин добавим вершины с аппликатами из отрезка [0,1].

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

Это некорректное рассуждение, которое ничего не доказывает.

На основании того, что к конечному графу можно добавить одну вершину делается совершенно необоснованный вывод о том, что к нему можно добавить континуум вершин. Между тем максимум, что отсюда можно выжать --- это возможность вложить в $\mathbb{R}^3$ полный граф со счётным числом вершин (да и то надо будет дополнительно отметить, что объединение возрастающей цепочки конечных полных графов есть счётный полный граф).

Вот пример аналогичного рассуждения, приводящего к явно абсурдному выводу.

К любому конечному множеству непересекающихся шаров радиуса $1$ можно добавить ещё один шар такого же радиуса, непересекающийся с остальными. Действительно, добавим его произвольным образом. Если он пересекается с одним из уже имеющихся, отодвинем его на достаточно далёкое от остальных шаров расстояние.

А теперь просто к пустому множеству шаров добавим шары единичного радиуса, центры которых имеют аппликаты из отрезка $[0,1]$.

Получается, что в $\mathbb{R}^3$ можно вложить континуум шаров радиуса $1$, не пересекающихся между собой

[ddn]

Профессор Снэйп писал(а):

2) Доказать, что в $\mathbb{R}^3$ можно вложить полный граф, имеющий континуум вершин.

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

У меня есть родственная проблема: Существует ли для любого иньективного отображения $\mathbb{R}^n$ ($n>1$) в себя: $g(x)$, семейство иньективных отображений $\mathbb{R}^n$ в себя: $f(x,t)$ ($x \in \mathbb{R}^n$ и $t \in [0,1]$), переводящих тождественное отображение $id_{\mathbb{R}^n}$ в данное отображение $g(x)$ непрерывно для каждой точки $x$ (то есть $f(x,t)$ непрерывно по $t$). Никакой непрерывности $g(x)$ и $f(x,t)$ по $x$ не требуется, они могут быть совершенно разрывными!
Тоже самое можно поставить для биективных отображений (дополнительно потребовав сюрьективности).

То есть в пространстве $\mathbb{R}^n$ начинают непрерывно двигаться точки, не задевая друг друга. Могут ли они поменять свое местоположение самым произвольным образом (условие биективности - точки все время покрывают все пространство)

Если возможно таким образом отобразить плоскость в одну из ее прямых, то проблема элементарно решена для любых $n>1$ для иньективных отображений (но не биективных) - так как точки прямой в рамках содержащей ее плоскости можно произвольным образом переставить (двигая каждую точку непрерывно и не задевая точки), в три этапа: сначала точку $(x_0,0)$ (которую необходимо перевести $(x_1,0)$) прямолинейно перемещаем в $(x_0,x_1)$, а после перевода всех точек прямолинейно перемещаем в $(0,x_1)$, потом, после перевода всех точек, возвращаем на первоначальную прямую в положение $(x_1,0)$ поворотом.

Справедливо ли для биективных отображений, что положительное решение проблемы на плоскости элементарно решает проблему для любых $n>2$.
Вот одно неполное доказательство по индукции: Пусть $z$ - все коодинаты точки, кроме двух: $x$ и $y$. В пределах каждой гиперплоскости $x=const$ передвигаем точку $(x_0,y_0,z_0)$ (которую необходимо перевести$(x_1,y_1,z_1)$) в некоторое место на прямой $x=x_0, z=z_1$, а потом в каждой плоскости $z=const$ передвигаем точку в требующееся место $(x_1,y_1,z_1)$, единственная "кочка" - точек какой-нибудь гиперплоскости $x=x_0$, которые на промежуточном этапе отобразятся в какую-нибудь прямую $x=x_0, z=z_1$ может оказаться меньше континуума и сюрьективность отображения нарушиться.

[Someone]

ddn писал(а):

Профессор Снэйп писал(а):

2) Доказать, что в $\mathbb{R}^3$ можно вложить полный граф, имеющий континуум вершин.

... Проведем ребро от каждой вершины к другой вершине в сопоставленной ей полуплоскости в виде полуокружности, где отрезок соединяющий вершины является диаметром, а если полуплоскости сопоставляем парам вершин, то за ребро можно взять любую простую непрерывную кривую, пересекающую нашу прямую только на своих концах - этой в паре вершин.

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

ddn писал(а):

Если вершины заданы призвольно, при соблюдении некоторых ограничений (например, они образуют нигде не плотное множество), то это превращается в очень и очень сложную топологическую проблему. Боюсь, что ни один современный математик решить ее не сможет.

Для нигде не плотного множества вершин ответ отрицательный (пусть это множество есть сфера в $\mathbb R^3$ плюс ещё две точки - одна внутри и одна снаружи).

А вот о Вашей "родственной" проблеме ничего сказать не могу.

[ddn]

Someone писал(а):

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

Думаю, в качестве множества вершин можно взять даже некую простую пространственную кривую, возможно даже неограниченной длины (все ее хорды, не должны пересекаться внутренними точками).

Someone писал(а):

Для нигде не плотного множества вершин ответ отрицательный (пусть это множество есть сфера в $\mathbb R^3$ плюс ещё две точки - одна внутри и одна снаружи).

Да, значит нужны более сложные условия.

Someone писал(а):

А вот о Вашей "родственной" проблеме ничего сказать не могу.

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

[Someone]

ddn писал(а):

Думаю, в качестве множества вершин можно взять даже некую простую пространственную кривую, возможно даже неограниченной длины (все ее хорды, не должны пересекаться внутренними точками).

Да. Там всего лишь требуется, чтобы никакие 4 точки не лежали в одной плоскости. Годится, например, кривая, задаваемая параметрическими уравнениями $x=t,\ y=t^2, z=t^3$. Наверное, что-то подобное можно устроить с суперграфом в $\mathbb R^5$.

ddn писал(а):

Someone писал(а):

А вот о Вашей "родственной" проблеме ничего сказать не могу.

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

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

Я буду рассматривать случай, когда область определения отображение $g$ совпадает с $\mathbb R^n$, где $n\geqslant 2$, и отображение $g\colon\mathbb R^n\to\mathbb R^n$ сюръективно. В конце я скажу, что изменится, если этих предположений не делать.

Перенумеруем все точки $\mathbb R^3$ ординалами, меньшими первого ординала мощности континуум. Точку с номером $\alpha$ будем обозначать $r_{\alpha}$. Также перенумеруем теми же ординалами все точки $\mathbb R^n\times(0,1)$. Точку с номером $\alpha$ будем обозначать $(\rho_{\alpha},t_{\alpha})$.
Наша задача состоит в том, чтобы соединить каждую точку $(r_{\alpha},0)$ с точкой $(g(r_{\alpha}),1)$ непрерывной линией $(f(r_{\alpha},t),t)$, $0\leqslant t\leqslant 1$, так, чтобы эти линии не пересекались и покрывали всё множество $\mathbb R^n\times[0,1]$.
Построение начнём с того, что соединим прямолинейными отрезками точку $(\rho_0,t_0)$ с точками $(r_0,0)$ и $(g(r_0),1)$, и обозначим $M_0$ множество прямых, на которых лежат уже построенные отрезки (две или одна - если три указанные точки лежат на одной прямой).
Предположим, что $\alpha>0$, и что для всех ординалов $\gamma<\alpha$ уже построены ломаные, соединяющие точки $(r_{\gamma},0)$ и $(g(r_{\gamma}),1)$, и каждая из точек $(\rho_{\gamma},t_{\gamma})$ лежит на одной из построенных ломаных. Обозначим $M'_{\alpha}=\bigcup\{M_{\gamma}:\gamma<\alpha\}$. Для произвольной точки $(r,t)\in\mathbb R^3\times[0,1]$ обозначим $L'(r,t)$ множество тех прямых из $M'_{\alpha}$, которые проходят через $(r,t)$, и $L''(r,t)$ - множество (двумерных) плоскостей, проходящих через точку $(r,t)$ и те прямые из $M'_{\alpha}$, которые не проходят через точку $(r,t)$. Заметим, что множества $L'(r,t)$ и $L''(r,t)$ имеют мощность строго меньше континуума.
Если точка $(\rho_{\alpha},t_{\alpha})$ не лежит ни на одной из уже построенных ломаных, то рассмотрим ($n$-мерную) гиперплоскость $t=\frac{t_{\alpha}}2$. Эта гиперплоскость пересекается с плоскостями из множеств $L''(r_{\alpha},0)$ и $L''(\rho_{\alpha},t_{\alpha})$ по множеству прямых, имеющему мощность меньше континуума, поэтому можно выбрать прямую, не совпадающую ни с одной из них; выбранная прямая пересекается с указанными прямыми, а также с прямыми из множеств $L'(r_{\alpha},0)$ и $L'(\rho_{\alpha},t_{\alpha})$, по множеству, имеющему мощность меньше континуума, поэтому на выбранной прямой найдётся точка $(s,\frac{t_{\alpha}}2)$, не принадлежащая ни одной из прямых и плоскостей из множеств $L'(r_{\alpha},0)$, $L'(\rho_{\alpha},t_{\alpha})$, $L''(r_{\alpha},0)$ и $L''(\rho_{\alpha},t_{\alpha})$. Соединим точку $(s,\frac{t_{\alpha}}2)$ с точками $(r_{\alpha},0)$ и $(\rho_{\alpha},t_{\alpha})$ прямолинейными отрезками. Эти отрезки не пересекаются с ранее построенными отрезками, лежащими на прямых, не проходящих через точку $(r_{\alpha},0)$ или $(\rho_{\alpha},t_{\alpha})$, так как не лежат в одной плоскости с этими прямыми, и не пересекаются с ранее построенными отрезками, лежащими на прямых, проходящих через точку $(r_{\alpha},0)$ или $(\rho_{\alpha},t_{\alpha})$, так как такое пересечение могло бы произойти только в соответствующей точке $(r_{\alpha},0)$ или $(\rho_{\alpha},t_{\alpha})$, а она не принадлежит ни одному из ранее построенных отрезков. Далее таким же способом соединяем ломаной точку $(\rho_{\alpha},t_{\alpha})$ с точкой $(g(r_{\gamma}),1)$, используя гиперплоскость $t=\frac{t_{\alpha}+1}2$.
Если же точка $(\rho_{\alpha},t_{\alpha})$ уже лежит на одной из построенных ломаных, то её игнорируем и соединяем точку $(r_{\alpha},0)$ с точкой $(g(r_{\gamma}),1)$, используя гиперплоскость $t=\frac 12$.
Множество $M_{\alpha}$ получим, добавив к множеству $M'_{\alpha}$ прямые, на которых лежат отрезки, построенные на шаге $\alpha$. Это множество имеет мощность, меньшую континуума, и мы можем продолжать построение дальше.
Выполнив построение для всех ординалов, имеющих мощность, меньшую континуума, получим требуемое семейство ломаных (заметим, что каждая из них состоит не более чем из 4 отрезков).

Если отображение $g$ определено не на всём $\mathbb R^n$, то нумеровать ординалами нужно только область определения $g$. Если мощность этой области определения равна континууму, то мы по-прежнему можем добиться того, чтобы отображение $g_t(x)=f(x,t)$ было биективным при всех $t\in(0,1)$ (а при $t=0$ и при $t=1$ - в зависимости от заданного $g$).

P.S. А чем Вы занимаетесь, что у Вас такая задача возникла? Или это просто любопытство?

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

Someone писал(а):

ddn писал(а):

... Проведем ребро от каждой вершины к другой вершине в сопоставленной ей полуплоскости в виде полуокружности, где отрезок соединяющий вершины является диаметром, а если полуплоскости сопоставляем парам вершин, то за ребро можно взять любую простую непрерывную кривую, пересекающую нашу прямую только на своих концах - этой в паре вершин.

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

Совершенно верно, речь шла именно о прямолинейных отрезках. Цитирую условие (нужное место выделил жирным шрифтом)

Профессор Снэйп писал(а):

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

Как уже было замечено, в качестве примера континуального полного графа, вложенного в $\mathbb{R}^3$, годится множество точек $\{ \langle t, t^2, t^3 \rangle : t \in \mathbb{R} \}$.

[ddn]

Someone писал(а):

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

Мда... Проверил. Корректно. Спасибо.
Вы заставили проходить пути через каждую точку $\mathbb{R}^n\times(0,1)$, а дальше дело техники. Я ведь тоже люблю использовать трансфинитную индукцию, по поводу и без повода. Но я пытался применить ее только для моментов времени $t \in [0,1]$ и строил отображение сразу для всех точек $x \in \mathbb{R}^n$. Для счетного, всюду плотного подмножества из $[0,1]$ я нужное отображение построил, а дальше автоматически, продолжение по непрерывности и... безо всякой гарантии его иньективности. А ведь так просто. Нужно было только заменить процесс во времени, на статическую задачу в $\mathbb{R}^n\times(0,1)$. Обленился я.

Someone писал(а):

Если отображение $g$ определено не на всём $\mathbb R^n$, то нумеровать ординалами нужно только область определения $g$. Если мощность этой области определения равна континууму, то мы по-прежнему можем добиться того, чтобы отображение $g_t(x)=f(x,t)$ было биективным при всех $t\in (0,1)$ (а при $t=0$ и при $t=1$ - в зависимости от заданного $g$).

Вообще-то, меня интересовал случай, когда область значений $g$ не есть все $\mathbb R^n$. Но ваше построение решает и это, даже с излишком (промежуточной биективностью).

Someone писал(а):

P.S. А чем Вы занимаетесь, что у Вас такая задача возникла? Или это просто любопытство?

Занимаюсь я физикой элементарных частиц, а интересуюсь я непрофессионально (в смысле, неуглубленно) разными науками, в том числе, много чем из математики.
Возникла задачка из моей топологическо-геометрической фантазии. Вобщем, в году может 94-м, еще до моего студентчества. Изучил я первую свою книжку по теории множеств Александрова, размышлял о бесконечностях. Бесконечное множество есть, как известно, взаимнооднозначно отображаемое на свое собственное подмножество. Прочел я, какие-то там конструктивные сложности возникают, чтобы доказать, что счетно-бесконечное множество - минимальное из бесконечных (требовалась аксиома выбора). Нужно, думаю, для доказательства оного утверждения, сделать отображение бесконечного множества в себя, затрагивающим минимальное (счетное) число элементов, причем сделать это конструктивно. Даже интересно потребовать, чтобы собственное подмножество было меньше всего на один элемент, то есть отображение было по типу $x_{n} \to x_{n+1}$ на неком счетном подмножестве и постоянное на остальных элементах. Для наглядности, я работал с плоскостью (в воображении) - здесь-то конечно постороить конструктивный пример проще простого, но... я всегда размышляю над топологическими задачками, и над теоретико-множественными как правило тоже, без бумаги, умозрительно. И я пытался построить такой пример отображения плоскости в себя с помощью непрерывных передвижений ее точек, и без наползаний точек друг на друга - ибо так нагляднее. Но не получалось. Я сначала использовал простейшие перемещения: выбирал какую-нибудь прямую, полупрямую или окружность и сдвигал ее точки как целое (сохраняя расстояния), а затем комбинации этих движений. Получалось перемещение континуума точек, а при отображении в себя (сдвиг полупрямой) всегда "оголялось" также континнум точек, а не одна. Я даже заинтересовался, а можно подвергнуть перемещению только конечное число точек? - можно. Можно даже поменять местами две любые точки, передвигая только две окружности. Мне это напомнило одну детскую пластмассовую игрушку в виде "крендельков" (забыл название) - это пересечение двух и более окружностей, в которых проделаны желобки и туда помещены шарики и их можно было перемещать скопом. А можно ли с помощью счетного числа комбинаций таких простейших движений изменить положение только счетного числа точек и так, чтобы появилось "оголение" плоскости?, а притом в одной точке? Тогда я не нашел ответ на этот вопрос, и не смог бы найти. Сейчас наверно смог бы, даже, пожалуй, без бумажки. Но тогда не смог, может тогда мне и пришла в голову мысль, рассмотреть такие движения точек в самом общем виде. Можно ли конструктивно построить такое движение точек плоскости, что "оголяется" всего одна точка плоскости, а испытывет перемещение лишь счетное их число? А может эта мысль, рассмотреть такие движения точек в самом общем виде, возникла у меня позже и была навеяна геометрической программой Клейна, где всяческие преобразования, стягивания, рассматриваются как цепь непрерывных движений, деформаций фигур в рамках некоторого пространства. Даже пытались топологию так рассмотреть (гомеоморфизмы между топ-пространствами) - не получилось, ибо программа Клейна не универсальна. А почему бы, подумалось, и обычные взаимнооднозначные отображения между множествами так не рассмотреть, в рамках некоторого топ-пространства?

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

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