Вопрос про размерность

[Mikhail_K]

Мне интересен следующий вопрос.

Есть $n$-мерный куб (или даже не куб, а всё $n$-мерное пространство, как удобнее).
Он разбит на достаточно большое (может быть, очень большое) количество областей неправильной формы.

Можно наложить любые естественные условия: например, что области не могут сильно отличаться по диаметрам, грубо говоря, диаметр одной области не может быть в сто раз больше диаметра другой. Или любое другое условие подобного вида, если оно поможет решить задачу. Например, если $n=2$, допустимы стандартные замощения квадратами, шестиугольниками (вдали от границы квадрата), и т.д.

Дальше составляется граф: каждой области ставится в соответствие вершина графа, если две области соседствуют, то соответствующие вершины соединяются ребром.

И вот вопрос: можно ли, имея этот граф, определить или оценить размерность $n$?

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

Можно представить себе, что есть мир, разбитый на страны. Мы знаем в точности, какие страны соседние. Можно ли что-то сказать о размерности этого мира?

[Narn]

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

[ИСН]

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

[Mikhail_K]

Narn, расскажите подробнее, пожалуйста. Что значит "для любого набора областей сообщу, пусто их пересечение или нет"?
Граф как раз и показывает, какие области соприкасаются частью границы, какие нет.

[Someone]

Mikhail_K в сообщении #1015553 писал(а):

И вот вопрос: можно ли, имея этот граф, определить или оценить размерность $n$?

В такой формулировке, как у Вас, вряд ли что-то разумное можно сказать.

Но аналогичная характеристика размерности существует: П. С. Александров, Б. А. Пасынков. Введение в теорию размерности."Наука", Москва, 1973. Глава 2, § 2.

[Утундрий]

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

[Narn]

Ну, я об открытых покрытиях думаю. Пусть $\{U_i\}$ --- такое покрытие. Ваш граф всего лишь говорит мне, верно ли, что $U_i \cap U_j$ пусто. А вот про тройки $U_i \cap U_j \cap U_k$, четверки, и прочие он уже никакой информации не содержит.

[Mikhail_K]

Someone в сообщении #1015573 писал(а):

В такой формулировке, как у Вас, вряд ли что-то разумное можно сказать.

Но аналогичная характеристика размерности существует: П. С. Александров, Б. А. Пасынков. Введение в теорию размерности."Наука", Москва, 1973. Глава 2, § 2.

На своей формулировке не настаиваю, можно её варьировать.
Книгу посмотрю.

[Утундрий]

Narn
Вот зачем вы инцидентность на пересечение заменили, а?

[Mikhail_K]

Narn в сообщении #1015579 писал(а):

Ну, я об открытых покрытиях думаю. Пусть $\{U_i\}$ --- такое покрытие. Ваш граф всего лишь говорит мне, верно ли, что $U_i \cap U_j$ пусто. А вот про тройки $U_i \cap U_j \cap U_k$, четверки, и прочие он уже никакой информации не содержит.

Прекрасно! Пусть известно всё что надо про тройки, четвёрки и т.д. Что тогда можно сказать?

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

[Narn]

В общем, если вы сообщите для каждой $n$-ки, пусто ее пересечение или нет, и вдобавок сообщите, какие из элементов покрытия ограничены, то можно будет, исходя из этого, посчитать гомологии одноточечной компактификации $\mathbb{R}^d$. С другой стороны, эта компактификация --- это $d$-мерная сфера, и ненулевые гомологии у нее лишь в 0 и в $d$, так вы и узнаете $d$. Как-то так.

Update. Поправил буквы --- непустоту пересечения надо знать для любого кортежа, и использованная там $n$ никакого отношения к размерности $d$ не имеет. Прошу прощения.

[Narn]

Утундрий в сообщении #1015582 писал(а):

Narn
Вот зачем вы инцидентность на пересечение заменили, а?

А ведь и правда Вообще, если мы потребуем, чтобы все элементы покрытия $\{ F_i \}$ были выпуклыми замкнутыми множествами с непустой внутренностью, пересекающимися лишь по границе, и построим граф, в котором между $F_i$ и $F_j$ есть ребро тогда и только тогда, когда $F_i \cap F_j$ непусто (из графа, в котором между $F_i$ и $F_j$ нет ребра, если их пересечение состоит только из одной точки, мы нужной информации не извлечем), то этого достаточно, вроде бы. Ведь тогда можно смотреть на покрытие $\{A_i\}$, полученное очень малым раздутием $F_i$, и при этом $A_{i_1} \cap A_{i_2} \dots \cap A_{i_k}$ непусто в точности когда все $F_{i_1}, \dots, F_{i_k}$ друг с другом попарно пересекаются, то есть образуют клику в графе. Значит, весь нерв покрытия мы знаем из графа. Но без информации о том, какие элементы покрытия неограничены (или, для куба --- пересекаются с его границей), все равно не обойтись.

[Narn]

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

[Mikhail_K]

Narn, почему?

И ещё, посоветуйте литературу, из которой можно научиться "посчитать гомологии одноточечной компактификации".

[Narn]

Вот к этому вранью очень легко привести контрпример:

Narn в сообщении #1015768 писал(а):

при этом $A_{i_1} \cap A_{i_2} \dots \cap A_{i_k}$ непусто в точности когда все $F_{i_1}, \dots, F_{i_k}$ друг с другом попарно пересекаются, то есть образуют клику в графе.

Почитать можно какой-нибудь учебник по алг. топологии. В статье википедии http://en.wikipedia.org/wiki/%C4%8Cech_cohomology
ссылка на Хэтчера, к примеру (стандартный учебник нынче, есть русский перевод, можно разжиться в сети). Есть еще хорошая книжка Edelsbrunner, Harer, Computational Topology. В сети доступен, насколько я знаю, ее черновой вариант. Она может показаться вам сильно проще.

Вообще, если вы можете выбирать постановку задачи (а я из вашего стартового поста понял, что у вас большая свобода в этом плане), то проще всего будет брать регулярные покрытия из маленьких множеств и делать по совету ИСН (это, в принципе, называется "размерность Хаусдорфа"). Общетопологическое определение размерности (в книге Александрова-Пасынкова) --- это, по-моему, чистейшая теория, с ее помощью эффективно считать, хоть на бумаге человеку, хоть на машине, очень сложно. Подход через гомологии требует, возможно, самых больших усилий на предварительную подготовку, но вполне реализуем, в том числе и в виде комп. программ (собственно, Эделсьбруннер-Харер про это).