2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

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



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Вопрос про размерность
Сообщение15.05.2015, 17:18 
Заслуженный участник
Аватара пользователя


26/01/14
4601
Мне интересен следующий вопрос.

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

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

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

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

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

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

 Профиль  
                  
 
 Re: Вопрос про размерность
Сообщение15.05.2015, 17:38 


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

 Профиль  
                  
 
 Re: Вопрос про размерность
Сообщение15.05.2015, 17:42 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Вопрос про размерность
Сообщение15.05.2015, 17:45 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Вопрос про размерность
Сообщение15.05.2015, 17:49 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
Mikhail_K в сообщении #1015553 писал(а):
И вот вопрос: можно ли, имея этот граф, определить или оценить размерность $n$?
В такой формулировке, как у Вас, вряд ли что-то разумное можно сказать.

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

 Профиль  
                  
 
 Re: Вопрос про размерность
Сообщение15.05.2015, 17:49 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Вопрос про размерность
Сообщение15.05.2015, 17:53 


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

 Профиль  
                  
 
 Re: Вопрос про размерность
Сообщение15.05.2015, 17:56 
Заслуженный участник
Аватара пользователя


26/01/14
4601
Someone в сообщении #1015573 писал(а):
В такой формулировке, как у Вас, вряд ли что-то разумное можно сказать.

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


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

 Профиль  
                  
 
 Re: Вопрос про размерность
Сообщение15.05.2015, 17:57 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Вопрос про размерность
Сообщение15.05.2015, 18:00 
Заслуженный участник
Аватара пользователя


26/01/14
4601
Narn в сообщении #1015579 писал(а):
Ну, я об открытых покрытиях думаю. Пусть $\{U_i\}$ --- такое покрытие. Ваш граф всего лишь говорит мне, верно ли, что $U_i \cap U_j$ пусто. А вот про тройки $U_i \cap U_j \cap U_k$, четверки, и прочие он уже никакой информации не содержит.


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

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

 Профиль  
                  
 
 Re: Вопрос про размерность
Сообщение15.05.2015, 18:03 


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

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

 Профиль  
                  
 
 Re: Вопрос про размерность
Сообщение15.05.2015, 22:48 


28/05/08
284
Трантор
Утундрий в сообщении #1015582 писал(а):
Narn
Вот зачем вы инцидентность на пересечение заменили, а?

А ведь и правда :oops: Вообще, если мы потребуем, чтобы все элементы покрытия $\{ 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}$ друг с другом попарно пересекаются, то есть образуют клику в графе. Значит, весь нерв покрытия мы знаем из графа. Но без информации о том, какие элементы покрытия неограничены (или, для куба --- пересекаются с его границей), все равно не обойтись.

 Профиль  
                  
 
 Re: Вопрос про размерность
Сообщение16.05.2015, 22:54 


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

 Профиль  
                  
 
 Re: Вопрос про размерность
Сообщение16.05.2015, 23:11 
Заслуженный участник
Аватара пользователя


26/01/14
4601
Narn, почему?

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

 Профиль  
                  
 
 Re: Вопрос про размерность
Сообщение17.05.2015, 00:06 


28/05/08
284
Трантор
Вот к этому вранью очень легко привести контрпример:
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. В сети доступен, насколько я знаю, ее черновой вариант. Она может показаться вам сильно проще.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 16 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group