|
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.
Received: 05.07.2018 Revised: 05.07.2018 Accepted: 17.08.2018
Citation:
O. V. Borodin, A. O. Ivanova, “Low faces of restricted degree in $3$-polytopes”, Sibirsk. Mat. Zh., 60:3 (2019), 527–536; Siberian Math. J., 60:3 (2019), 405–411
Linking options:
https://www.mathnet.ru/eng/smj3093 https://www.mathnet.ru/eng/smj/v60/i3/p527
|
Statistics & downloads: |
Abstract page: | 290 | Full-text PDF : | 35 | References: | 40 | First page: | 6 |
|