Низкие грани ограниченной степени в $3$-многогранниках
О. В. Бородин,
А. О. Иванова Институт математики им. С. Л. Соболева СО РАН, пр. Академика Коптюга, 4, Новосибирск 630090
Аннотация:
Степень вершины или грани в
$3$-многограннике есть число инцидентных ей ребер.
$k$-Грань есть грань степени
$k$, а
$k^-$-грань имеет степень не более
$k$. Высота грани — максимальная степень инцидентных ей вершин, а высота
$h$ многогранника — минимальная из высот его граней. Грань называется
пирамидальной, если она является либо
$4$-гранью, инцидентной трем
$3$-вершинам, либо
$3$-гранью, инцидентной двум вершинам степени не более четырех. Если пирамидальные грани разрешены, то
$h$ может быть произвольно большой, поэтому в дальнейшем предполагается отсутствие пирамидальных граней.
В 1940 г. Лебег доказал, что в каждом четыреангулированном
$3$-многограннике найдется грань
$f$ с
$h(f)\le 11$. В 1995 г. эта оценка была улучшена С. В. Августиновичем и О. В. Бородиным до
$10$. Недавно мы улучшили эту оценку до точной оценки
$8$. Для плоских триангуляций без
$4$-вершин О. В. Бородин (1992) подтвердил гипотезу Коцига 1979 г., доказав, что
$h\le 20$, причем оценка точна. Позднее О. В. Бородин доказал, что
$h\le 20$ для всех триангулированных
$3$-многогранников. В 1996 г. для произвольных многогранников Хорняк и Йендроль доказали, что
$h\le 23$. Недавно мы получили точные оценки
$h\le 10$ для многогранников без треугольников и
$h\le 20$ для произвольных многогранников. Позже О. В. Бородин, М. А. Быков и А. О. Иванова улучшили последний результат, доказав, что любой многогранник содержит
$10^-$-грань высоты не более
$20$, причем обе оценки
$10$ и
$20$ точны. Также мы доказали, что любой многогранник содержит
$5^-$-грань высоты не более
$30$, где оценка
$30$ точна и улучшает верхнюю оценку
$39$, полученную Хорняком и Йендролем (1996).
В статье доказано, что каждый многогранник содержит
$6^-$-грань высоты не более
$22$, где параметры
$6$ и
$22$ неулучшаемы. Поскольку существует конструкция, в которой каждая грань степени от
$6$ до
$9$ имеет высоту
$22$, теперь известно все, что касается максимальных высот граней ограниченных степеней в
$3$-многогранниках.
Ключевые слова:
плоская карта, плоский граф, $3$-многогранник, структурные свойства, высота грани, степень грани.
УДК:
519.17
MSC: 35R30 Статья поступила: 05.07.2018
Окончательный вариант: 05.07.2018
Принята к печати: 17.08.2018
DOI:
10.33048/smzh.2019.60.305