Эта публикация цитируется в
1 статье
Математика
Двусторонние оценки существенной высоты в теореме Ширшова о высоте
М. И. Харитонов Московский государственный университет имени М. В. Ломоносова, механико-математический факультет
Аннотация:
Работа посвящена получению двусторонних оценок существенной высоты в условиях теоремы Ширшова о высоте. Вводятся понятия выборочной высоты и сильной
$n$-разбиваемости, непосредственно связанные с высотой и
$n$-разбиваемостью, и доказываются нижние и верхние оценки выборочной высоты над не сильно
$n$-разбиваемыми словами длины
$2$, причем эти оценки различаются лишь в
$2$ раза при любом
$n$ и достаточно большом
$l$. Также разбирается случай слов длины
$3$. Разбор случая слов длины
$2$ можно обобщить до доказательства экспоненциальной верхней оценки в теореме Ширшова. Доказательство использует идею В. Н. Латышева, связанную с применением теоремы Дилуорса к исследованию не
$n$-разбиваемых слов.
Ключевые слова:
существенная высота, теорема Ширшова о высоте, комбинаторика слов,
$n$-разбиваемость, теорема Дилуорса.
УДК:
512.552.4+
512.57+
519.1 Поступила в редакцию: 27.06.2011