Search

It is trivial that every 3-polytope has a face of degree at most 5, called minor. Back in 1940, Lebesgue gave an approximate description of minor faces in 3-polytopes, depending on 17 main parameters. In 2002, Borodin improved Lebesgue’s description on six parameters without worsening the others and suggested to find a tight description of minor faces. So far, such a tight description has been obtained only for several restricted classes of 3-polytopes: those with minimum degree 5 (Borodin, 1989), without vertices of degree 3 (Borodin and Ivanova, 2013), for plane triangulations (Borodin et al. 2014), and without vertices of degree from 4 to 7 (Borodin et al. 2017). In this paper, we consider 3-polytopes without vertices of degree from 5 to 7. A face is of type ( k 1 , k 2 , … ) if the set of degrees of its incident vertices is majorized by the vector ( k 1 , k 2 , … ) . It follows from results by Horňak and Jendrol’ (1996) that every such polytope has a face of one of the types ( 4 , 4 , ∞ ) , ( 3 , 8 , 15 ) , ( 3 , 9 , 14 ) , ( 3 , 10 , 13 ) , ( 3 , 3 , 3 , ∞ ) , ( 3 , 3 , 4 , 11 ) , ( 3 , 4 , 4 , 4 ) , and ( 3 , 3 , 3 , 3 , 4 ) , which improves four parameters in what can be obtained from Lebesgue’s description. We prove a tight description “ ( 4 , 4 , ∞ ) , ( 3 , 8 , 14 ) , ( 3 , 9 , 13 ) , ( 3 , 10 , 12 ) , ( 3 , 3 , 3 , ∞ ) , ( 3 , 3 , 4 , 11 ) , ( 3 , 4 , 4 , 4 ) , ( 3 , 3 , 3 , 3 , 4 ) ” and, in particular, give constructions (unexpected for us) showing that 13 and 11 here are best possible (constructions confirming the sharpness of the other parameters were known before).

In 1940, Lebesgue proved that every 3-polytope with minimum degree 5 contains a 5-vertex for which the set of degrees of its neighbors is majorized by one of the following sequences: ( 6 , 6 , 7 , 7 , 7 ) , ( 6 , 6 , 6 , 7 , 9 ) , ( 6 , 6 , 6 , 6 , 11 ) , ( 5 , 6 , 7 , 7 , 8 ) , ( 5 , 6 , 6 , 7 , 12 ) , ( 5 , 6 , 6 , 8 , 10 ) , ( 5 , 6 , 6 , 6 , 17 ) , ( 5 , 5 , 7 , 7 , 13 ) , ( 5 , 5 , 7 , 8 , 10 ) , ( 5 , 5 , 6 , 7 , 27 ) , ( 5 , 5 , 6 , 6 , ∞ ) , ( 5 , 5 , 6 , 8 , 15 ) , ( 5 , 5 , 6 , 9 , 11 ) , ( 5 , 5 , 5 , 7 , 41 ) , ( 5 , 5 , 5 , 8 , 23 ) , ( 5 , 5 , 5 , 9 , 17 ) , ( 5 , 5 , 5 , 10 , 14 ) , ( 5 , 5 , 5 , 11 , 13 ) . Recently, we proved that forbidding vertices of degree from 7 to 11 results in a tight description ( 5 , 5 , 6 , 6 , ∞ ) , ( 5 , 6 , 6 , 6 , 15 ) , ( 6 , 6 , 6 , 6 , 6 ) . The purpose of this note is to prove that every 3-polytope with minimum degree 5 and no vertices of degrees 6, 7, and 8 has a 5-vertex whose neighborhood is majorized by one of the sequences ( 5 , 5 , 5 , 5 , ∞ ) and ( 5 , 5 , 5 , 10 , 12 ) , which is tight and improves a corresponding description ( 5 , 5 , 5 , 5 , ∞ ) , ( 5 , 5 , 9 , 5 , 17 ) , ( 5 , 5 , 10 , 5 , 14 ) , ( 5 , 5 , 11 , 5 , 13 ) that follows from the Lebesgue Theorem.

An edge e in a 3-polytope is of type ( k 1 , k 2 , k 3 , k 4 ) if the set of degrees of the vertices and faces incident with e is majorized by the vector ( k 1 , k 2 , k 3 , k 4 ) . In 1940, Lebesgue proved that every 3-polytope has an edge of one of the types ( 3 , 3 , 3 , ∞ ) , ( 3 , 3 , 4 , 11 ) , ( 3 , 3 , 5 , 7 ) , ( 3 , 4 , 4 , 5 ) . This also provides a description of the faces of quadrangulated 3-polytopes in terms of degrees of their incident vertices. The purpose of our paper is to prove that every 3-polytope has an edge of one of the types ( 3 , 3 , 3 , ∞ ) , ( 3 , 3 , 4 , 9 ) , ( 3 , 3 , 5 , 6 ) , ( 3 , 4 , 4 , 5 ) , where all parameters except possibly 9 are best possible. We believe that 9 here is sharp and thus the whole description is tight. Our proof relies on the discharging method.

It is trivial that every 3-polytope has a face of degree at most 5, called minor. The height h ( f ) of a face f is the maximum degree of the vertices incident with f . It follows from the partial double n -pyramids that h ( f ) can be arbitrarily large for each f if a 3-polytope is allowed to have faces of types ( 4 , 4 , ∞ ) or ( 3 , 3 , 3 , ∞ ) . In 1996, M. Horňak and S. Jendrol’ proved that every 3-polytope without faces of types ( 4 , 4 , ∞ ) and ( 3 , 3 , 3 , ∞ ) has a minor face of height at most 39 and constructed such a 3-polytope satisfying h ( f ) ≥ 30 for all minor faces f . The purpose of this paper is to prove that every 3-polytope without faces of types ( 4 , 4 , ∞ ) and ( 3 , 3 , 3 , ∞ ) has a minor face of height at most 30, which bound is tight due to the Horňak–Jendrol’ construction.

We present 35 open problems on combinatorial, geometric and algebraic aspects of k -orbit abstract polytopes. We also present a theory of rooted polytopes that has appeared implicitly in previous work but has not been formalized before.

Given a 3-polytope P , by h ( P ) we denote the minimum of the maximum degrees (height) of the neighborhoods of 5-vertices (minor 5-stars) in P . In 1940, H. Lebesgue gave an approximate description of the neighborhoods of 5-vertices in the class P 5 of 3-polytopes with minimum degree 5. In 1996, S. Jendrol’ and T. Madaras showed that if a polytope P in P 5 is allowed to have a 5-vertex adjacent to four 5-vertices (called a minor ( 5 , 5 , 5 , 5 , ∞ ) -star), then h ( P ) can be arbitrarily large. For each P ∗ in P 5 with neither vertices of degree 6 or 7 nor minor ( 5 , 5 , 5 , 5 , ∞ ) -star, it follows from Lebesgue’s theorem that h ( P ∗ ) ≤ 23 . We prove that every such polytope P ∗ satisfies h ( P ∗ ) ≤ 14 , which bound is sharp. Moreover, if 6-vertices are allowed but 7-vertices forbidden, or vice versa, then the height of minor 5-stars in P 5 under the absence of minor ( 5 , 5 , 5 , 5 , ∞ ) -stars can reach 15 or 17, respectively.

Divided symmetrization of a function f ( x 1 , … , x n ) is symmetrization of the ratio D S G ( f ) = f ( x 1 , … , x n ) ∏ ( x i − x j ) , where the product is taken over the set of edges of some graph G . We concentrate on the case when G is a tree and f is a polynomial of degree n − 1 , in this case D S G ( f ) is a constant function. We give a combinatorial interpretation of the divided symmetrization of monomials for general trees and probabilistic game interpretation for a tree which is a path. In particular, this implies a result by Postnikov originally proved by computing volumes of special polytopes, and suggests its generalization.

Given an abstract n-polytope K , an abstract ( n + 1 ) -polytope P is an extension of K if all the facets of P are isomorphic to K . A chiral polytope is a polytope with maximal rotational symmetry that does not admit any reflections. If P is a chiral extension of K , then all but the last entry of the Schlafli symbol of P are determined. In this paper we introduce some constructions of chiral extensions P of certain chiral polytopes in such a way that the last entry of the Schlafli symbol of P is arbitrarily large.

The first chiral polytope of full rank known was Roli’s cube, a rank 4 polytope discovered in 2014. Since then, other chiral polytopes of rank 4 have been studied. Here we present the first known chiral 5-polytope of full rank. Its 2-skeleton is the same as that of the Euclidean tessellation { 3 , 4 , 3 , 3 } with 24-cells.

Let w Δ be the minimum integer W with the property that every 3-polytope with minimum degree 5 and maximum degree Δ has a vertex of degree 5 with the degree-sum (weight) of all vertices in its closed neighborhood at most W . Trivially, w 5 = 30 and w 6 = 35 . In 1940, Lebesgue proved w Δ ≤ Δ + 31 for all Δ ≥ 5 and w Δ ≤ Δ + 27 for Δ ≥ 41 . In 1998, the first Lebesgue’s result was improved by Borodin and Woodall to w Δ ≤ Δ + 30 . This bound is sharp for Δ = 7 due to Borodin (1992) and Jendrol’ and Madaras (1996), Δ = 9 due to Borodin and Ivanova (2013), Δ = 10 due to Jendrol’ and Madaras (1996), and Δ = 12 due to Borodin and Woodall (1998). As for the second Lebesgue’s bound, Borodin et al. (2014) proved that w Δ ≤ Δ + 27 for Δ ≥ 28 , but w 20 ≥ 48 ; the former fact was extended by Borodin and Ivanova (2016) to w Δ ≤ Δ + 27 for Δ ≥ 23 . The purpose of this paper is to prove w Δ ≤ Δ + 29 whenever Δ ≥ 13 and show that w 8 = 38 , w 11 = 41 , and w 13 = 42 . Thus w Δ remains unknown only for 14 ≤ Δ ≤ 22 .

In 1940, in attempts to solve the Four Color Problem, H. Lebesgue gave an approximate description of the neighborhoods of 5-vertices in the class P 5 of 3-polytopes with minimum degree 5. Given a 3-polytope P , by h ( P ) we denote the minimum of the maximum degrees (height) of the neighborhoods of 5-vertices (minor 5-stars) in P . In 1996, S. Jendrol’ and T. Madaras showed that if a polytope P in P 5 is allowed to have a 5 -vertex adjacent to four 5-vertices, then h ( P ) can be arbitrarily large. For each P without vertices of degree 6 and 5 -vertices adjacent to four 5-vertices in P 5 , it follows from Lebesgue’s Theorem that h ( P ) ≤ 41 . Recently, this bound was lowered to h ( P ) ≤ 28 by O. Borodin, A. Ivanova, and T. Jensen and then to h ( P ) ≤ 23 by O. Borodin and A. Ivanova. In this paper, we prove that every such polytope P satisfies h ( P ) ≤ 17 , which bound is sharp.

The f -vector of a polytope consists of the numbers of its i -dimensional faces. An open field of study is the characterization of all possible f -vectors. It has been solved in three dimensions by Steinitz in the early 19th century. We state a related question, i.e., to characterize f -vectors of three dimensional polytopes respecting a symmetry, given by a finite group of matrices. We give a full answer for all three dimensional polytopes that are symmetric with respect to a finite rotation or rotary reflection group. We solve these cases constructively by developing tools that generalize Steinitz’s approach.

The weight of a face in a 3-polytope is the degree-sum of its incident vertices, and the weight of a 3-polytope, w , is the minimum weight 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 w can be arbitrarily large, so we assume the absence of pyramidal faces in what follows.In 1940, Lebesgue proved that every quadrangulated 3-polytope has w ź 21 . In 1995, this bound was lowered by Avgustinovich and Borodin to 20. Recently, we improved it to the sharp bound 18.For plane triangulations without 4-vertices, Borodin (1992), confirming the Kotzig conjecture of 1979, proved that w ź 29 , which bound is sharp. Later, Borodin (1998) proved that w ź 29 for all triangulated 3-polytopes. Recently, we obtained the sharp bound 20 for triangle-free polytopes.In 1996, Horňak and Jendrol' proved for arbitrarily polytopes that w ź 32 . In this paper we improve this bound to 30 and construct a polytope with w = 30 .

We address the problem of completability for 2-row orthogonal Latin rectangles ( O L R 2 ). Our approach is to identify all pairs of incomplete 2-row Latin rectangles that are not completable to an O L R 2 and are minimal with respect to this property; i.e.,?we characterize all circuits of the independence system associated with O L R 2 . Since there can be no polytime algorithm generating the clutter of circuits of an arbitrary independence system, our work adds to the few independence systems for which that clutter is fully described. The result has a direct polyhedral implication; it gives rise to inequalities that are valid for the polytope associated with orthogonal Latin squares and thus planar multi-dimensional assignment. A complexity result is also at hand: completing a set of ( n - 1 ) incomplete M O L R 2 is NP -complete.

The height h ( e ) of an edge e in a 3-polytope is the maximum degree of the two vertices and two faces incident with e . In 1940, Lebesgue proved that every 3-polytope without so called pyramidal edges has an edge e with h ( e ) ? 11 . In 1995, this upper bound was improved to 10 by Avgustinovich and Borodin. Recently, we improved it to 9 and constructed a 3-polytope without pyramidal edges satisfying h ( e ) ? 8 for each e .The purpose of this paper is to prove that every 3-polytope without pyramidal edges has an edge e with h ( e ) ? 8 .In different terms, this means that every plane quadrangulation without a face incident with three vertices of degree 3 has a face incident with a vertex of degree at most 8, which is tight.

An upper bound on the diameter of the Stable Matching (Stable Marriage) polytope is known to be ⌊ n 2 ⌋ where n is the number of men (or women) involved in the matching. The current work complements that result by providing a lower bound and an algorithm computing it. It also presents a class of Stable Matching instances for which the lower bound coincides with the above-mentioned upper bound.

We give a set of conditions that is necessary and sufficient for the existence and uniqueness up to translations of a 3-dimensional polytope P in R 3 having N facets with given unit outward normal vectors n 1 , … , n N and corresponding facet perimeters L 1 , … , L N .

In Parts I–III we showed that the number of ways to place q nonattacking queens or similar chess pieces on an n × n chessboard is a quasipolynomial function of n whose coefficients are essentially polynomials in q . In this part we focus on the periods of those quasipolynomials. We calculate denominators of vertices of the inside-out polytope, since the period is bounded by, and conjecturally equal to, their least common denominator. We find an exact formula for that denominator of every piece with one move and of two-move pieces having a horizontal move. For pieces with three or more moves, we produce geometrical constructions related to the Fibonacci numbers that show the denominator grows at least exponentially with q .

In this paper, we study the flag graph FG ( P ) of a regular abstract polytope P from two aspects of Cayley graphs: Hamiltonicity and Cayley index. We show that FG ( P ) has a Hamiltonian cycle, and introduce the Cayley index of P as the fraction | A ut ( FG ( P ) ) | ∕ | Γ ( P ) | , where Γ ( P ) is the automorphism group of P . A new construction of arc-transitive tetravalent graphs will be described by means of regular abstract polyhedra of Cayley index larger than 1. In addition, polyhedra of type { p , q } such that p ≤ 5 or q ≤ 5 that have Cayley index larger than 1 are characterized.

To classify the lattice polytopes with a given $\delta$-polynomial is an important open problem in Ehrhart theory. A complete classification of the Gorenstein simplices whose normalized volumes are prime integers is known. In particular, their $\delta$-polynomials are of the form $1+t^k+\cdots+t^{(v-1)k}$, where $k$ and $v$ are positive integers. In the present paper, a complete classification of the Gorenstein simplices with the above $\delta$-polynomials will be performed, when $v$ is either $p^2$ or $pq$, where $p$ and $q$ are prime integers with $p \neq q$. Moreover, we consider the number of Gorenstein simplices, up to unimodular equivalence, with the expected $\delta$-polynomial., Comment: 14 pages, to appear in Discrete Mathematics

Let w"P(C"l) (w"T(C"l)) be the minimum integer k with the property that every 3-polytope (respectively, every plane triangulation) with minimum degree 5 has an l-cycle with weight, defined as the degree-sum of all vertices, at most k. In 1998, O.V. Borodin and D.R. Woodall proved w"T(C"4)=25 and w"T(C"5)=30. We prove that w"P(C"4)=26 and w"P(C"5)=30.

The monodromy group is an important tool for encoding and understanding the combinatorial structure of polytopes, both convex and abstract. In the current work we investigate the structure of the monodromy groups of the infinite family of pyramids over n-gons, as well as the structure of their minimal regular covers.

Let @f"P(C"6) (respectively, @f"T(C"6)) be the minimum integer k with the property that every 3-polytope (respectively, every plane triangulation) with minimum degree 5 has a 6-cycle with all vertices of degree at most k. In 1999, S. Jendrol' and T. Madaras proved that [email protected][email protected]"T(C"6)@?11. It is also known, due to B. Mohar, R. Skrekovski and H.-J. Voss (2003), that @f"P(C"6)@?107. We prove that @f"P(C"6)[email protected]"T(C"6)=11.

We generalize the classical notion of majorization in R n to a majorization order for functions defined on a partially ordered set P . In this generalization we use inequalities for partial sums associated with ideals in P . Basic properties are established, including connections to classical majorization. Moreover, we investigate transfers (given by doubly stochastic matrices), complexity issues and associated majorization polytopes.

An extended formulation of a polytope P is a polytope Q which can be projected onto P. Extended formulations of small size (i.e., number of facets) are of interest, as they allow to model corresponding optimization problems as linear programs of small sizes. The main known lower bounds on the minimum sizes of extended formulations for fixed polytope P (Yannakakis 1991) are closely related to the concept of nondeterministic communication complexity. We study the relative power and limitations of the bounds on several examples., Revision, 25pp

We prove that any simple polytope (and some non-simple polytopes) in R 3 admits a regular octahedron inscribed into its surface.

We classify the bicyclic polytopes and their vertex figures, up to combinatorial equivalence. These four-dimensional polytopes, which were previously studied by Smilansky, admit abelian groups of orientation-preserving symmetries that act transitively on their vertices. The bicyclic polytopes come in both simplicial and nonsimplicial varieties. It is noteworthy that their facial structures admit an explicit and complete presentation. Their vertex figures are also of interest, and they play a prominent role in the classification; their combinatorial structures are studied in detail here. The f-vectors of the polytopes and of their vertex figures are given.

International audience; Given an undirected graph G, a uniform cut polytope is defined as the convex hull of the incidence vectors of the cuts in G for which the size of the shores are fixed. In this paper we show that simple extensions of facet-defining inequalities for the equipartition polytope introduced by Conforti et al. in [5] and [6] provide facet-defining inequalities for uniform cut polyhedra.

Minkowski's second theorem on successive minima gives an upper bound on the volume of a convex body in terms of its successive minima. We study the problem to generalize Minkowski's bound by replacing the volume by the lattice point enumerator of a convex body. In this context we are interested in bounds on the coefficients of Ehrhart polynomials of lattice polytopes via the successive minima. Our results for lattice zonotopes and lattice-face polytopes imply, in particular, that for 0-symmetric lattice-face polytopes and lattice parallelepipeds the volume can be replaced by the lattice point enumerator., 16 pages, incorporated referee remarks, corrected proof of Theorem 1.2, added new co-author

We consider the problem of clustering a set of items into subsets whose sizes are bounded from above and below. We formulate the problem as a graph partitioning problem and propose an integer programming model for solving it. This formulation generalizes several well-known graph partitioning problems from the literature like the clique partitioning problem, the equi-partition problem and the k-way equi-partition problem. In this paper, we analyze the structure of the corresponding polytope and prove several results concerning the facial structure. Our analysis yields important results for the closely related equi-partition and k-way equi-partition polytopes as well. (C) 2010 Elsevier B.V. All rights reserved.

Let [email protected]?R^N be an integral convex polytope of dimension d and @d(P)=(@d"0,@d"1,...,@d"d) its @d-vector. It is known that @?"j"="0^[email protected]"d"-"[email protected][email protected]?"j"="0^[email protected]"j"+"1 for each [email protected][email protected]?[(d-1)/2]. A @d-vector @d(P)=(@d"0,@d"1,...,@d"d) is called shifted symmetric if @?"j"="0^[email protected]"d"-"[email protected]?"j"="0^[email protected]"j"+"1 for each [email protected][email protected]?[(d-1)/2], i.e., @d"d"-"[email protected]"i"+"1 for each [email protected][email protected]?[(d-1)/2]. In this paper, some properties of integral convex polytopes with shifted symmetric @d-vectors will be studied. Moreover, as a natural family of those, (0,1)-polytopes will be introduced. In addition, shifted symmetric @d-vectors with (0,1)-vectors are classified when @?"i"="0^[email protected]"[email protected]?5.

In this paper we describe a construction for chiral polytopes with preassigned regular facets. Furthermore we show that this construction implies the existence of chiral d-polytopes, for every rank d≥3.

Obtaining a complete description of the stable set polytopes of claw-free graphs is a long-standing open problem. Eisenbrand et al. recently achieved a breakthrough for the subclass of quasi-line graphs. As a consequence, every non-trivial facet of their stable set polytope has at most two different, but arbitrarily high left hand side coefficients. For the graphs with stability number 2, Cook showed that all their non-trivial facets are 1/2-valued. For claw-free but not quasi-line graphs with stability number at least 4, Stauffer conjectured that the same holds true. In contrast, there are known claw-free graphs with stability number 3 which induce facets with up to eight different left hand side coefficients. We prove that the situation is even worse: for every positive integer b, we exhibit a claw-free graph with stability number 3 inducing a facet with b different left hand side coefficients.

The profile vector f(U)∈Rn+1 of a family U of subspaces of an n-dimensional vector space V over GF(q) is a vector of which the ith coordinate is the number of subspaces of dimension i in the family U(i=0,1,…,n). In this paper, we determine the profile polytope of intersecting families (the convex hull of the profile vectors of all intersecting families of subspaces).

Let X^2^m be one of the spaces of constant curvature and @C be a discrete and finitely presented subgroup of Iso(X^2^m). We combine Schlafli's reduction formula and Poincare's formula with the cycle condition to get a formula for the covolume of @C which only depends on the combinatorics of a fundamental polytope for @C and the orders of certain stabilizer subgroups of @C.

For some graph classes defined by forbidding one-vertex extensions of the P"4, we introduce an implicit description of the stable set polytope; furthermore, for some of those classes, we give explicitly a minimal defining linear system. This is of interest since the class of P"4-free graphs is basic in modular decomposition theory, and at the same time a well-known result of Chvatal [V. Chvatal, On certain polytopes associated with graphs, Journal of Combinatorial Theory Series (B) 18 (1975) 138-154] provides a strict link between modular decomposition of graphs and their stable set polytope.

There are only finitely many locally projective regular polytopes of type {5, 3, 5}. They are covered by a locally spherical polytope whose automorphism group is J1×J1×L2(19), where J1 is the first Janko group, of order 175560, and L2(19) is the projective special linear group of order 3420. This polytope is minimal, in the sense that any other polytope that covers all locally projective polytopes of type {5, 3, 5} must in turn cover this one.

Hilbert's 17th Problem launched a number of inquiries into sum-of-squares representations of polynomials over the real numbers. Choi, Lam, and Reznick gave some bounds on the number of squares required for such a representation and indicated some directions for improving these bounds. In the first part of this paper, we follow their suggestion and obtain some stronger bounds. In the second part, we show that in the case of homogeneous polynomials in three variables, this technique cannot be extended further.