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

Sibirsk. Mat. Zh., 2019 Volume 60, Number 3, Pages 527–536 (Mi smj3093)

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


 English version:
Siberian Mathematical Journal, 2019, 60:3, 405–411

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024