RUS  ENG
Full version
JOURNALS // Sibirskii Matematicheskii Zhurnal // Archive

Sibirsk. Mat. Zh., 2021 Volume 62, Number 2, Pages 250–268 (Mi smj7554)

Heights of minor faces in 3-polytopes

O. V. Borodin, A. O. Ivanova

Sobolev Institute of Mathematics, Novosibirsk, Russia

Abstract: Each 3-polytope has obviously a face $f$ of degree $d(f)$ at most 5 which is called minor. The height $h(f)$ of $f$ is the maximum degree of the vertices incident with $f$. A type of a face $f$ is defined by a set of upper constraints on the degrees of vertices incident with $f$. This follows from the double $n$-pyramid and semiregular $(3,3,3,n)$-polytope, $h(f)$ can be arbitrarily large for each $f$ if a 3-polytope is allowed to have faces of types $(4,4,\infty)$ or $(3,3,3,\infty)$ which are called pyramidal. Denote the minimum height of minor faces in a given 3-polytope by $h$. In 1996, Horňák and Jendrol' proved that every 3-polytope without pyramidal faces satisfies $h\le39$ and constructed a 3-polytope with $h=30$. In 2018, we proved the sharp bound $h\le30$. In 1998, Borodin and Loparev proved that every 3-polytope with neither pyramidal faces nor $(3,5,\infty)$-faces has a face $f$ such that $h(f)\le20$ if $d(f)=3$, or $h(f)\le11$ if $d(f)=4$, or $h(f)\le5$ if $d(f)=5$, where bounds 20 and 5 are best possible. We prove that every 3-polytope with neither pyramidal faces nor $(3,5,\infty)$-faces has $f$ with $h(f)\le20$ if $d(f)=3$, or $h(f)\le10$ if $d(f)=4$, or $h(f)\le5$ if $d(f)=5$, where all bounds 20, 10, and 5 are best possible.

Keywords: graph, plane graph, 3-polytope, structural properties, minor face, degree, height, weight.

UDC: 519.17

MSC: 35R30

Received: 31.08.2020
Revised: 14.11.2020
Accepted: 18.11.2020

DOI: 10.33048/smzh.2021.62.202


 English version:
Siberian Mathematical Journal, 2021, 62:2, 199–214

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024