|
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.
Received: 31.08.2020 Revised: 14.11.2020 Accepted: 18.11.2020
Citation:
O. V. Borodin, A. O. Ivanova, “Heights of minor faces in 3-polytopes”, Sibirsk. Mat. Zh., 62:2 (2021), 250–268; Siberian Math. J., 62:2 (2021), 199–214
Linking options:
https://www.mathnet.ru/eng/smj7554 https://www.mathnet.ru/eng/smj/v62/i2/p250
|
Statistics & downloads: |
Abstract page: | 217 | Full-text PDF : | 28 | References: | 33 | First page: | 1 |
|