Polyhedra related to a lattice

Without using the l.p. duality theorem, we give a new and direct proof that Hoffman's lattice polyhedra, polyhedra from problems of Edmonds and Giles, and others, are integer. These polyhedra are intersections of more simple polyhedra such that every vertex of the initial polyhedron is a vertex of some simple polyhedron. In many cases encountered in combinatorics the simple polyhedra have a totally unimodular constraint matrix. This implies that all vertices of the initial polyhedron are integral. The proof is based on a theorem on submodular functions, which was not known earlier. The method of this paper can be applied to the consideration of the matching polyhedron.     

Oscillatory integral decay, sublevel set growth, and the Newton polyhedron

Extending some resolution of singularities methods (Greenblatt in J Funct Anal 255(8):1957–1994, 2008) of the author, a generalization of a well-known theorem of Varchenko (Funct Anal Appl 18(3):175–196, 1976) relating decay of oscillatory integrals to the Newton polyhedron is proven. They are derived from analogous results for sublevel integrals, proven here. Varchenko’s theorem requires a certain nondegeneracy condition on the faces of the Newton polyhedron on the phase. In this paper, it is shown that the estimates of Varchenko’s theorem also hold for a significant class of phase functions for which this nondegeneracy condition does not hold. Thus in problems where one wants to switch coordinates to a coordinate system where Varchenko’s estimates are valid, one has greater flexibility. Some additional estimates are also proven for more degenerate situations, including some too degenerate for the Newton polyhedron to give the optimal decay in the sense of Varchenko.     

A multidimensional generalization of Lagrange’s theorem on continued fractions

A multidimensional geometric analog of Lagrange’s theorem on continued fractions is proposed. The multidimensional generalization of the geometric interpretation of a continued fraction uses the notion of a Klein polyhedron, that is, the convex hull of the set of nonzero points in the lattice ? ⁿ contained inside some n-dimensional simplicial cone with vertex at the origin. A criterion for the semiperiodicity of the boundary of a Klein polyhedron is obtained, and a statement about the nonempty intersection of the boundaries of the Klein polyhedra corresponding to a given simplicial cone and to a certain modification of this cone is proved.     

Polynomials and spatial Pick-type theorems

Pick's theorem about the area of a simple lattice planar polygon has many extensions and generalizations even in the planar case. The theorem has also higher-dimensional generalizations, which are not as commonly known as the 2-dimensional case. The aim of the paper is, on one hand, to give a few new higher-dimensional generalizations of Pick's theorem and, on the other hand, collect known ones. We also study some relationships between lattice points in a lattice polyhedron which lead to some new Pick-type formulae. Another purpose of this paper is to pose several problems related to the subject of higher-dimensional Pick-type theorems. We hope that the paper may popularize the idea of determining the volume of a lattice polyhedron P by reading information contained in a lattice and the tiling of the space generated by the lattice.     

Positivity of curvature and convexity of faces

Two-dimensional polyhedra homeomorphic to closed two-dimensional surfaces are considered in the three-dimensional Euclidean space. While studying the structure of an arbitrary face of a polyhedron, an interesting particular case is revealed when the magnitude of only one plane angle determines the sign of the curvature of the polyhedron at the vertex of this angle. Due to this observation, the following main theorem of the paper is obtained: If a two-dimensional polyhedron in the three-dimensional Euclidean space is isometric to the surface of a closed convex three-dimensional polyhedron, then all faces of the polyhedron are convex polygons.     

Analytic proofs of a network feasibility theorem and a theorem of Fulkerson

We provide an elementary proff of Fulkerson's theorem which gives the permutation matrices as extreme points of a certain unbounded convex polyhedron. An adaptation of the proof also establishes an analogous feasibility theorem for network flows which has Fulkerson's theorem as a corollary.     

Minimal half-spaces and external representation of tropical polyhedra

We give a characterization of the minimal tropical half-spaces containing a given tropical polyhedron, from which we derive a counter-example showing that the number of such minimal half-spaces can be infinite, contradicting some statements which appeared in the tropical literature, and disproving a conjecture of F. Block and J. Yu. We also establish an analogue of the Minkowski–Weyl theorem, showing that a tropical polyhedron can be equivalently represented internally (in terms of extreme points and rays) or externally (in terms of half-spaces containing it). A canonical external representation of a polyhedron turns out to be provided by the extreme elements of its tropical polar. We characterize these extreme elements, showing in particular that they are determined by support vectors.     

Short proofs on the matching polyhedron

A short proof of Edmonds' matching polyhedron theorem and the total dual integrality of the associated system of linear inequalities, proved first by W. H. Cunningham and A. B. Marsh (Math. Programming Stud.8 (1978), 50–72), is given.     

Surfaces in a pseudo-Euclidean space

A survey of results on regular and nonregular surfaces in a three-dimensional pseudo-Euclidean space. The method of approximating a convex surface by polyhedra and the intrinsic construction of polyhedra of negative curvature are considered in detail. A theorem on the existence in a pseudo-Euclidean space of a convex polyhedron with given polyhedral metric of negative curvature with a finite number of vertices is proved.Translated from Itogi Nauki i Tekhniki, Seriya Problemy Geometrii, Vol. 11, pp. 177–202, 1980.     

Finding feasible vectors of Edmonds-Giles polyhedra

A combinatorial algorithm for finding a feasible vector of the Edmonds-Giles polyhedron is presented. The algorithm is polynomially bounded provided that an oracle is available for minimizing submodular functions. A feasibility theorem is also proved by the algorithm and, as a consequence, a good algorithm for finding an integer-valued modular function between a sub- and a supermodular function is deduced. An important idea in the algorithm is due to Schönsleben and Lawler and Martel: the shortest augmenting paths have to be chosen in a lexicographic order.     

Degree matrices and divisibility of exponential sums over finite fields

By using the degree matrix, we provide an elementary and algorithmic approach to estimating the divisibility of exponential sums over prime fields, which improves the Adolphson–Sperber theorem obtained by using the Newton polyhedron. Our result also improves the Ax–Katz theorem on estimating the number of rational points on hypersurfaces over prime fields.     

确定线性规划全部最优解的方法

使用凸多面体的表示定理 ,导出了标准型线性规划最优解的一般表达式 ,并基于单纯形法 ,给出最优解唯一性条件以及当唯一性条件不满足时求出全部最优解的计算步骤 ,同时附有数值例子 .     

An isoperimetric problem for tetrahedra

It is proved that a regular tetrahedron has the maximal possible surface area among all tetrahedra having surface with unit geodesic diameter. An independent proof of O’Rourke-Schevon’s theorem about polar points on a convex polyhedron is given. A. D. Aleksandrov’s general problem on the area of a convex surface with fixed geodesic diameter is discussed. Bibliography: 4 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 329, 2005, pp. 28–55.     

A combinatorial formula for affine Hall–Littlewood functions via a weighted Brion theorem

We present a new combinatorial formula for Hall–Littlewood functions associated with the affine root system of type \({{\tilde{A}}}_{n-1}\), i.e., corresponding to the affine Lie algebra \({{\widehat{\mathfrak {sl}}}}_n\). Our formula has the form of a sum over the elements of a basis constructed by Feigin, Jimbo, Loktev, Miwa and Mukhin in the corresponding irreducible representation. Our formula can be viewed as a weighted sum of exponentials of integer points in a certain infinite-dimensional convex polyhedron. We derive a weighted version of Brion’s theorem and then apply it to our polyhedron to prove the formula.     

Note on: N.E. Aguilera, M.S. Escalante, G.L. Nasini, “The disjunctive procedure and blocker duality”

Aguilera et al. [Discrete Appl. Math. 121 (2002) 1–13] give a generalization of a theorem of Lehman through an extension of the disjunctive procedure defined by Balas, Ceria and Cornuéjols. This generalization can be formulated as(A) For every clutter , the disjunctive index of its set covering polyhedron coincides with the disjunctive index of the set covering polyhedron of its blocker, .In Aguilera et al. [Discrete Appl. Math. 121 (2002) 1–3], (A) is indeed a corollary of the stronger result(B) .Motivated by the work of Gerards et al. [Math. Oper. Res. 28 (2003) 884–885] we propose a simpler proof of (B) as well as an alternative proof of (A), independent of (B). Both of them are based on the relationship between the “disjunctive relaxations” obtained by and the set covering polyhedra associated with some particular minors of .     

On a generalization of the master cyclic group polyhedron

We study the master equality polyhedron (MEP) which generalizes the master cyclic group polyhedron (MCGP) and the master knapsack polyhedron (MKP). We present an explicit characterization of the polar of the nontrivial facet-defining inequalities for MEP. This result generalizes similar results for the MCGP by Gomory (1969) and for the MKP by Araóz (1974). Furthermore, this characterization gives a polynomial time algorithm for separating an arbitrary point from MEP. We describe how facet-defining inequalities for the MCGP can be lifted to obtain facet-defining inequalities for MEP, and also present facet-defining inequalities for MEP that cannot be obtained in such a way. Finally, we study the mixed-integer extension of MEP and present an interpolation theorem that produces valid inequalities for general mixed integer programming problems using facets of MEP.     

DANZER-GRüNBAUM'S THEOREM REVISITED

In this paper we prove some stronger versions of Danzer-Grünbaum's theorem including the following stability-type result. For 0 < α < 14π/27 the maximum number of vertices of a convex polyhedron in E ³ such that all angles between adjacent edges are bounded from above by α is 8. One of the main tools is the spherical geometry version of Pál's theorem. This revised version was published online in August 2006 with corrections to the Cover Date.     

Rigidity of certain polyhedra in $ {\bold R}^3 $

We extend the Cauchy theorem stating rigidity of convex polyhedra in . We do not require that the polyhedron be convex nor embedded, only that the realization of the polyhedron in be linear and isometric on each face. We also extend the topology of the surfaces to include the projective plane in addition to the sphere. Our approach is to choose a convenient normal to each face in such a way that as we go around the star of a vertex the chosen normals are the vertices of a convex polygon on the unit sphere. When we can make such a choice at each vertex we obtain rigidity. For example, we can prove that the heptahedron is rigid. Received: March 3, 1999; revised: December 7, 1999.     

Dual row modules and polyhedra of blocking group problems

Corresponding to every group problem is a row module. Duality for group problems is developed using the duality or orthogonality of the corresponding row modules. The row module corresponding to a group problem is shown to include Gomory's fractional cuts for the group polyhedron and all the vertices of the polyhedron of the blocking group problem. The polyhedra corresponding to a pair of blocking group problems are shown to have a blocking nature i.e. the vertices of one include some of the facets of the other and mutatis mutandis. The entire development is constructive. The notions of contraction, deletion, expansion and extension are defined constructively and related to homomorphic liftings and suproblems in a dual setting. Roughly speaking a homomorphic lifting is dual to forming a subproblem. A proof of the Gastou-Johnson generalization of Gomory's homomorphic lifting theorem is given, and dual constructions are discussed. A generalization of Gomory's subadditive characterization to subproblems is given. In the binary case, it is closely related to the work of Seymour on cones arising from binary matroids.     

How to Exhibit Toroidal Maps in Space

Steinitz's theorem states that a graph is the 1-skeleton of a convex polyhedron if and only if it is 3-connected and planar. The polyhedron is called a geometric realization of the embedded graph. Its faces are bounded by convex polygons whose points are coplanar. A map on the torus does not necessarily have such a geometric realization. In this paper we relax the condition that faces are the convex hull of coplanar points. We require instead that the convex hull of the points on a face can be projected onto a plane so that the boundary of the convex hull of the projected points is the image of the boundary of the face. We also require that the interiors of the convex hulls of different faces do not intersect. Call this an exhibition of the map. A map is polyhedral if the intersection of any two closed faces is simply connected. Our main result is that every polyhedral toroidal map can be exhibited. As a corollary, every toroidal triangulation has a geometric realization.