Low faces of restricted degree in $3$-polytopes
O. V. Borodin,
A. O. Ivanova Sobolev Institute of Mathematics, Novosibirsk, Russia
Abstract:
The degree of a vertex or face in a
$3$-polytope is the number of incident edges. A
$k$-face is one of degree
$k$, a
$k^-$-face has degree at most
$k$. The height of a face is the maximum degree of its incident vertices; and the height of a
$3$-polytope,
$h$, is the minimum height of its faces. A face is pyramidal if it is either a
$4$-face incident with three
$3$-vertices or a
$3$-face incident with two vertices of degree at most
$4$. If pyramidal faces are allowed, then
$h$ can be arbitrarily large; and so we assume the absence of pyramidal faces in what follows. In 1940, Lebesgue proved that each quadrangulated
$3$-polytope has a face
$f$ with
$h(f) \leqslant 11$. In 1995, this bound was lowered by Avgustinovich and Borodin to
$10$. Recently, we improved it to the sharp bound
$8$. For plane triangulation without
$4$-vertices, Borodin (1992), confirming the Kotzig conjecture of 1979, proved that
$h \leqslant 20$, which bound is sharp. Later, Borodin proved that
$h \leqslant 20$ for all triangulated
$3$-polytopes. In 1996, Horňák and Jendrol' proved for arbitrarily polytopes that
$h \leqslant 23$. Recently, we obtained the sharp bounds
$h \leqslant 10$ for triangle-free polytopes and
$h \leqslant 20$ for arbitrary polytopes. Later, Borodin, Bykov, and Ivanova refined the latter result by proving that any polytope has a
$10^-$-face of height at most
$20$, where
$10$ and
$20$ are sharp. Also, we proved that any polytope has a
$5^-$-face of height at most
$30$, where
$30$ is sharp and improves the upper bound of
$39$ obtained by Horňák and Jendrol' (1996). In this paper we prove that every polytope has a
$6^-$-face of height at most
$22$, where
$6$ and
$22$ are best possible. Since there is a construction in which every face of degree from
$6$ to
$9$ has height
$22$, we now know everything concerning the maximum heights of restricted-degree faces in
$3$-polytopes.
Keywords:
plane map, planar graph, $3$-polytope, structural properties, height and degree of a face.
UDC:
519.17
MSC: 35R30 Received: 05.07.2018
Revised: 05.07.2018
Accepted: 17.08.2018
DOI:
10.33048/smzh.2019.60.305