A class of affinely equivalent Voronoi parallelohedra

Given any parallelohedron P, its affine class A (P), i.e., the set of all parallelohedra affinely equivalent to it, is considered. Does this affine class contain at least one Voronoi parallelohedron, i.e., a parallelohedron which is a Dirichlet domain for some lattice? This question, more commonly known as Voronoi’s conjecture, has remained unanswered for more than a hundred years. It is shown that, in the case where the subset of Voronoi parallelohedra in A (P) is nonempty, this subset is an orbifold, and its dimension (as a real manifold with singularities) is completely determined by its combinatorial type; namely, it is equal to the number of connected components of the so-called Venkov subgraph of the given parallelohedron. Nevertheless, the structure of this orbifold depends not only on the combinatorial properties of the parallelohedron but also on its affine properties.     

Degree bounded matroids and submodular flows

We consider two related problems, the Minimum Bounded Degree Matroid Basis problem and the Minimum Bounded Degree Submodular Flow problem. The first problem is a generalization of the Minimum Bounded Degree Spanning Tree problem: We are given a matroid and a hypergraph on its ground set with lower and upper bounds f(e)≤g(e) for each hyperedge e. The task is to find a minimum cost basis which contains at least f(e) and at most g(e) elements from each hyperedge e. In the second problem we have a submodular flow problem, a lower bound f(v) and an upper bound g(v) for each node v, and the task is to find a minimum cost 0–1 submodular flow with the additional constraint that the sum of the incoming and outgoing flow at each node v is between f(v) and g(v). Both of these problems are NP-hard (even the feasibility problems are NP-complete), but we show that they can be approximated in the following sense. Let opt be the value of the optimal solution. For the first problem we give an algorithm that finds a basis B of cost no more than opt such that f(e)?2Δ+1≤|B∩e|≤g(e)+2Δ?1 for every hyperedge e, where Δ is the maximum degree of the hypergraph. If there are only upper bounds (or only lower bounds), then the violation can be decreased to Δ?1. For the second problem we can find a 0–1 submodular flow of cost at most opt where the sum of the incoming and outgoing flow at each node v is between f(v)?1 and g(v)+1. These results can be applied to obtain approximation algorithms for several combinatorial optimization problems with degree constraints, including the Minimum Crossing Spanning Tree problem, the Minimum Bounded Degree Spanning Tree Union problem, the Minimum Bounded Degree Directed Cut Cover problem, and the Minimum Bounded Degree Graph Orientation problem.     

Polybasic polyhedra: structure of polyhedra with edge vectors of support size at most 2

It has widely been recognized that submodular set functions and base polyhedra associated with them play fundamental and important roles in combinatorial optimization problems. In the present paper, we introduce a generalized concept of base polyhedron. We consider a class of pointed convex polyhedra in R^V whose edge vectors have supports of size at most 2. We call such a convex polyhedron a polybasic polyhedron. The class of polybasic polyhedra includes ordinary base polyhedra, submodular/supermodular polyhedra, generalized polymatroids, bisubmodular polyhedra, polybasic zonotopes, boundary polyhedra of flows in generalized networks, etc. We show that for a pointed polyhedron PR^V, the following three statements are equivalent:

(1) P is a polybasic polyhedron.

(2) Each face of P with a normal vector of the full support V is obtained from a base polyhedron by a reflection and scalings along axes.

(3) The support function of P is a submodular function on each orthant of R^V.

This reveals the geometric structure of polybasic polyhedra and its relation to submodularity.     

On the Connection Between the Projection and the Extension of a Parallelotope

This paper presents a result concerning the connection between the parallel projection P _v,H of a parallelotope P along the direction v (into a transversal hyperplane H) and the extension P + S(v), meaning the Minkowski sum of P and the segment S(v) = {λv | −1 ≤ λ ≤ 1}. A sublattice L _v of the lattice of translations of P associated to the direction v is defined. It is proved that the extension P + S(v) is a parallelotope if and only if the parallel projection P _v,H is a parallelotope with respect to the lattice of translations L _v,H , which is the projection of the lattice L _v along the direction v into the hyperplane H.     

PATHS AND CYCLES EMBEDDING ON FAULTY ENHANCED HYPERCUBE NETWORKS

Let Qn,k(n≥3,1≤k≤n-1) be an n-dimensional enhanced hypercube which is an attractive variant of the hypercube and can be obtained by adding some complementary edges,fv and fe be the numbers of faulty vertices and faulty edges,respectively.In this paper,we give three main results.First,a fault-free path P [u,v] of length at least 2n-2fv-1(respectively,2n-2fv-2) can be embedded on Qn,k with fv+fe≤n-1 when d Qn,k(u,v) is odd(respectively,d Qn,k(u,v) is even).Secondly,an Qn,k is(n-2) edgefault-free hyper Hamiltonian-laceable when n(≥3) and k have the same parity.Lastly,a fault-free cycle of length at least 2n-2fv can be embedded on Qn,k with fe≤n-1 and fv+fe≤2n-4.     

Finite range decompositions of positive-definite functions

We give sufficient conditions for a positive-definite function to admit decomposition into a sum of positive-definite functions which are compactly supported within disks of increasing diameters Ln. More generally we consider positive-definite bilinear forms f→v(f,f) defined on . We say v has a finite range decomposition if v can be written as a sum v=∑Gn of positive-definite bilinear forms Gn such that Gn(f,g)=0 when the supports of the test functions f,g are separated by a distance greater or equal to Ln. We prove that such decompositions exist when v is dual to a bilinear form φ→∫²|Bφ| where B is a vector valued partial differential operator satisfying some regularity conditions.     

Increasing and decreasing operators on complete lattices

The (isotone) map f: X → X is an increasing (decreasing) operator on the poset X if f(x) ? f²(x) (f²(x) ? f(x), resp.) holds for each x ∈ X. Properties of increasing (decreasing) operators on complete lattices are studied and shown to extend and clarify those of closure (resp. anticlosure) operators. The notion of the decreasing closure, $\text{f}$, (the increasing anticlosure, $\text{f}$,) of the map f: X → X is introduced extending that of the transitive closure, $\text{f}\text{?}$, of f. $\text{f}\text{f}$, and $\text{f}$ are all shown to have the same set of fixed points. Our results enable us to solve some problems raised by H. Crapo. In particular, the order structure of H(X), the set of retraction operators on X is analyzed. For X a complete lattice H(X) is shown to be a complete lattice in the pointwise partial order. We conclude by claiming that it is the increasing-decreasing character of the identity maps which yields the peculiar properties of Galois connections. This is done by defining a u-v connection between the posets X and Y, where u: X → X (v: Y → Y) is an increasing (resp. decreasing) operator to be a pair f, g of maps f; X → Y, g: Y → X such that gf ? u, fg ? v. It is shown that the whole theory of Galois connections can be carried over to u-v connections.     

A proof of Coleman's conjecture

Almost thirty years ago Coleman made a conjecture that for any convex lattice polygon with v vertices, g (g?1) interior lattice points and b boundary lattice points we have b?2g-v+10. In this note we give a proof of the conjecture. We also aim to describe all convex lattice polygons for which the bound b=2g-v+10 is attained.     

Total edge irregularity strength of complete graphs and complete bipartite graphs

A total edge irregular k-labelling ν of a graph G is a labelling of the vertices and edges of G with labels from the set {1,…,k} in such a way that for any two different edges e and f their weights φ(f) and φ(e) are distinct. Here, the weight of an edge g=uv is φ(g)=ν(g)+ν(u)+ν(v), i. e. the sum of the label of g and the labels of vertices u and v. The minimum k for which the graph G has an edge irregular total k-labelling is called the total edge irregularity strength of G.We have determined the exact value of the total edge irregularity strength of complete graphs and complete bipartite graphs.     

Projective MV-algebras and rational polyhedra

Let M be an n-generator projective MV-algebra. Then there is a rational polyhedron P in the n-cube [0, 1] ⁿ such that M is isomorphic to the MV-algebra M(P){{\rm{\mathcal {M}}}(P)} of restrictions to P of the McNaughton functions of the free n-generator MV-algebra. P necessarily contains a vertex vP of the n-cube. We characterize those polyhedra contained in the n-cube such that M(P){{\mathcal {M}}(P)} is projective. In particular, if the rational polyhedron P is a union of segments originating at some fixed vertex vP of the n-cube, then M(P){{\mathcal {M}}(P)} is projective. Using this result, we prove that if A = M(P){A = {\mathcal {M}}(P)} and B = M(Q){B = {\mathcal {M}}(Q)} are projective, then so is the subalgebra of A × B given by {(f, g) | f(v _P ) = g(v _Q ), and so is the free product A \coprod B{A \coprod B} .     

Cellularity in polyhedra

A compact subset X of a polyhedron P is cellular in P if there is a pseudoisotropy of P shrinking precisely X to a point. A proper surjection between polyhedra f:P→Q is cellular if each point inverse of f is cellular in P. It is shown that if f:P→Q is a cellular map and either P or Q is a generalized n-manifold, n≠4, then f is approximable by homeomorphisms. Also, if P or Q is an n-manifold with boundary, n≠4, 5, then a cellular map f:P→Q is approximable by homeomorphisms. A cellularity criterion for a special class of cell-like sets in polyhedra is established.     

On convergence in mixed integer programming

Let ${P \subseteq {\mathbb R}^{m+n}}$ be a rational polyhedron, and let P _I be the convex hull of ${P \cap ({\mathbb Z}^m \times {\mathbb R}^n)}$ . We define the integral lattice-free closure of P as the set obtained from P by adding all inequalities obtained from disjunctions associated with integral lattice-free polyhedra in ${{\mathbb R}^m}$ . We show that the integral lattice-free closure of P is again a polyhedron, and that repeatedly taking the integral lattice-free closure of P gives P _I after a finite number of iterations. Such results can be seen as a mixed integer analogue of theorems by Chvátal and Schrijver for the pure integer case. One ingredient of our proof is an extension of a result by Owen and Mehrotra. In fact, we prove that for each rational polyhedron P, the split closures of P yield in the limit the set P _I .     

A descent method for submodular function minimization

We show a descent method for submodular function minimization based on an oracle for membership in base polyhedra. We assume that for any submodular function f: ?→R on a distributive lattice ?⊆2 ^V with ?,V∈? and f(?)=0 and for any vector x∈R ^V where V is a finite nonempty set, the membership oracle answers whether x belongs to the base polyhedron associated with f and that if the answer is NO, it also gives us a set Z∈? such that x(Z)>f(Z). Given a submodular function f, by invoking the membership oracle O(|V|²) times, the descent method finds a sequence of subsets Z ₁,Z ₂,···,Z _k of V such that f(Z ₁)>f(Z ₂)>···>f(Z _k )=min{f(Y) | Y∈?}, where k is O(|V|²). The method furnishes an alternative framework for submodular function minimization if combined with possible efficient membership algorithms. Received: September 9, 2001 / Accepted: October 15, 2001?Published online December 6, 2001     

Linear-time certifying algorithms for near-graphical sequences

A sequence 〈d₁,d₂,…,d_n〉 of non-negative integers is graphical if it is the degree sequence of some graph, that is, there exists a graph G on n vertices whose ith vertex has degree d_i, for 1≤i≤n. The notion of a graphical sequence has a natural reformulation and generalization in terms of factors of complete graphs.If H=(V,E) is a graph and g and f are integer-valued functions on the vertex set V, then a (g,f)-factor of H is a subgraph G=(V,F) of H whose degree at each vertex v∈V lies in the interval [g(v),f(v)]. Thus, a (0,1)-factor is just a matching of H and a (1, 1)-factor is a perfect matching of H. If H is complete then a (g,f)-factor realizes a degree sequence that is consistent with the sequence of intervals 〈[g(v₁),f(v₁)],[g(v₂),f(v₂)],…,[g(v_n),f(v_n)]〉.Graphical sequences have been extensively studied and admit several elegant characterizations. We are interested in extending these characterizations to non-graphical sequences by introducing a natural measure of “near-graphical”. We do this in the context of minimally deficient (g,f)-factors of complete graphs. Our main result is a simple linear-time greedy algorithm for constructing minimally deficient (g,f)-factors in complete graphs that generalizes the method of Hakimi and Havel (for constructing (f,f)-factors in complete graphs, when possible). It has the added advantage of producing a certificate of minimum deficiency (through a generalization of the Erdös-Gallai characterization of (f,f)-factors in complete graphs) at no additional cost.     

Klein polyhedra and relative minima of lattices

We prove that in ?³, the relative minima of almost any lattice belong to the surface of the corresponding Klein polyhedron. We also prove, for almost any lattice in ?³, that the set of relative minima with nonnegative coordinates coincides with the union of the set of extremal points of the Klein polyhedron and a set of special points belonging to the triangular faces of the Klein polyhedron.     

Calculus of convex polyhedra and polyhedral convex functions by utilizing a multiple objective linear programming solver

ABSTRACT

The article deals with operations defined on convex polyhedra or polyhedral convex functions. Given two convex polyhedra, operations like Minkowski sum, intersection and closed convex hull of the union are considered. Basic operations for one convex polyhedron are, for example, the polar, the conical hull and the image under affine transformation. The concept of a P-representation of a convex polyhedron is introduced. It is shown that many polyhedral calculus operations can be expressed explicitly in terms of P-representations. We point out that all the relevant computational effort for polyhedral calculus consists in computing projections of convex polyhedra. In order to compute projections we use a recent result saying that multiple objective linear programming (MOLP) is equivalent to the polyhedral projection problem. Based on the MOLP solver bensolve a polyhedral calculus toolbox for Matlab and GNU Octave is developed. Some numerical experiments are discussed.     

Lower negative decision number in a graph

Let G=(V,E) be a graph. A function f:V(G)→{?1,1} is called bad if ∑ _v∈N(v) f(v)≤1 for every v∈V(G). A bad function f of a graph G is maximal if there exists no bad function g such that g≠f and g(v)≥f(v) for every v∈V. The minimum of the values of ∑ _v∈V f(v), taken over all maximal bad functions f, is called the lower negative decision number and is denoted by β _D ^* (G). In this paper, we present sharp lower bounds on this number for regular graphs and nearly regular graphs, and we also characterize the graphs attaining those bounds.     

Sum List Coloring Graphs

Let G=(V,E) be a graph with n vertices and e edges. The sum choice number of G is the smallest integer p such that there exist list sizes (f(v):v ∈ V) whose sum is p for which G has a proper coloring no matter which color lists of size f(v) are assigned to the vertices v. The sum choice number is bounded above by n+e. If the sum choice number of G equals n+e, then G is sum choice greedy. Complete graphs K_n are sum choice greedy as are trees. Based on a simple, but powerful, lemma we show that a graph each of whose blocks is sum choice greedy is also sum choice greedy. We also determine the sum choice number of K_2,n, and we show that every tree on n vertices can be obtained from K_n by consecutively deleting single edges where all intermediate graphs are sc-greedy.     

Upper bounds on the upper signed total domination number of graphs

Let G=(V,E) be a graph. A function f:V→{−1,+1} defined on the vertices of G is a signed total dominating function if the sum of its function values over any open neighborhood is at least one. A signed total dominating function f is minimal if there does not exist a signed total dominating function g, f≠g, for which g(v)≤f(v) for every v∈V. The weight of a signed total dominating function is the sum of its function values over all vertices of G. The upper signed total domination number of G is the maximum weight of a minimal signed total dominating function on G. In this paper we present a sharp upper bound on the upper signed total domination number of an arbitrary graph. This result generalizes previous results for regular graphs and nearly regular graphs.     

The profile of the Cartesian product of graphs

Given a graph G, a proper labelingf of G is a one-to-one function from V(G) onto {1,2,…,|V(G)|}. For a proper labeling f of G, the profile widthw_f(v) of a vertex v is the minimum value of f(v)−f(x), where x belongs to the closed neighborhood of v. The profile of a proper labelingfofG, denoted by P_f(G), is the sum of all the w_f(v), where v∈V(G). The profile ofG is the minimum value of P_f(G), where f runs over all proper labeling of G. In this paper, we show that if the vertices of a graph G can be ordered to satisfy a special neighborhood property, then so can the graph G×Q_n. This can be used to determine the profile of Q_n and K_m×Q_n.