2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Изоморфизм произвольного конечного частичного порядка в R^n
Сообщение05.06.2017, 17:24 


08/09/13
210
Для $x,y \in {\mathbb R}^n$ определим "естественный" частичный порядок как $x \prec y \iff \left( \forall i:\ x_i \le y_i \right) \land \left( \exists j:\ x_i < y_j \right)$.
Произвольное конечное частично упорядоченное множество $A$ будем называть уложимым в ${\mathbb R}^n$ если существует изоморфизм $f:A \to {\mathbb R}^n$ такой, что $\forall a,b \in A:\ a \prec b \iff f(a) \prec f(b)$ (конечно, $\prec$ в левой части - это заданный порядок на множестве $A$, а в правой - определённый "естественный порядок").

Я задумался о том, насколько маленьким может быть множество $A$ чтобы оно гарантированно было уложимо в ${\mathbb R}^n$.
Контрпример с $|A|=2n+2$ для ${\mathbb R}^n$ строится относительно легко - это множество $A=\left\lbrace {a_1, \dots, a_{n+1}, b_1, \dots, b_{n+1}} \right\rbrace$, где $a_i \prec b_j \iff i \not = j$, а остальные пары элементов между собой не сравнимы.
Таким образом, нижняя граница требуемой размерности - $\frac{|A|}{2}$ (верхней границей легко получить $|A|$ - просто взять ортогональный базис и перенести в каждую вершину координаты из всех вершин, которые меньше неё).

Возникает вопрос, нижняя ли это граница. То есть: верно ли, что если $|A| \le 2n+1$, то его частичный порядок уложим в ${\mathbb R}^n$?

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

Кому интересно, давайте думать вместе.

 Профиль  
                  
 
 Re: Изоморфизм произвольного конечного частичного порядка в R^n
Сообщение05.06.2017, 18:16 
Заслуженный участник


18/01/15
3075
Во-первых, у Вас определение порядка странно выглядит, наверное в формуле $(\exists j: x_i<y_j)$ должно быть $x_j$, а не $x_i$. Во-вторых, слово "изоморфизм" тут не подходит, лучше писать "инъективное отображение"; а "изоморфизм" поразумевает биекцию. (но раньше, кстати, под изоморфизмом понимали любое вложение (инъекцию). Нынче же терминология изменилась). В третьих, ответ на вопрос, думаю, хорошо известен, посмотрите Айгнер "Комбинаторная теория", только не помню в каком именно месте. В четвертых, думать вместе вряд ли получится, но на такие случаи есть общий прием исследования: не пытаться сразу разрешить общий случай, а последовательно разбирать случаи $n=1$, $n=2$, $n=3$, $n=4$, и так далее, и в ходе этого заметите какую-нибудь общую закономерность (так всегда поступают, когда условие задачи зависит от одного или нескольких натуральных параметров).

 Профиль  
                  
 
 Re: Изоморфизм произвольного конечного частичного порядка в R^n
Сообщение05.06.2017, 18:25 
Заслуженный участник


16/02/13
4105
Владивосток
vpb в сообщении #1222420 писал(а):
насколько маленьким может быть множество $A$ чтобы оно гарантированно было уложимо в ${\mathbb R}^n$
Не понял вопроса. Ну, возьмите пустое множество $A$ — оно уложимо в любое ${\mathbb R}^n$, а меньше-то и некуда. Насколько большим, может?

 Профиль  
                  
 
 Re: Изоморфизм произвольного конечного частичного порядка в R^n
Сообщение05.06.2017, 18:33 


08/09/13
210
iifat в сообщении #1222426 писал(а):
Насколько большим, может?

Да, насколько большим.

vpb в сообщении #1222420 писал(а):
не пытаться сразу разрешить общий случай, а последовательно разбирать случаи

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

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



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

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


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

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