Alternatives for testing total dual integrality

In this paper we provide characterizing properties of totally dual integral (TDI) systems, among others the following: a system of linear inequalities is TDI if and only if its coefficient vectors form a Hilbert basis, and there exists a test-set for the system’s dual integer programs where all test vectors have positive entries equal to 1. Reformulations of this provide relations between computational algebra and integer programming and they contain Applegate, Cook and McCormick’s sufficient condition for the TDI property and Sturmfels’ theorem relating toric initial ideals generated by square-free monomials to unimodular triangulations. We also study the theoretical and practical efficiency and limits of the characterizations of the TDI property presented here. In the particular case of set packing polyhedra our results correspond to endowing the weak perfect graph theorem with an additional, computationally interesting, geometric feature: the normal fan of the stable set polytope of a perfect graph can be refined into a regular triangulation consisting only of unimodular cones.     

Structural properties and recognition of restricted and strongly unimodular matrices

A (0, ±1) matrix A is restricted unimodular if every matrix obtained from A by setting to zero any subset of its entries is totally unimodular. Restricted unimodular matrices are also known as matrices without odd cycles. They have been studied by Commoner and recently Yannakakis has given a polynomial algorithm to recognize when a matrix belongs to this class. A matrix A is strongly unimodular if any matrix obtained from A by setting at most one of its entries to zero is totally unimodular. Crama et al. have shown that (0,1) matrix A is strongly unimodular if and only if any basis of (A, 1) is triangular, whereI is an identity matrix of suitable dimensions. In this paper we give a very simple algorithm to test whether a matrix is restricted unimodular and we show that all strongly unimodular matrices can be obtained by composing restricted unimodular matrices with a simple operation. Partially supported by a New York University Research Challenge Fund Grant.     

A Normal (0, 1)-Polytope None of Whose Regular Triangulations Is Unimodular

A normal (0,1) -polytope none of whose regular triangulations is unimodular is constructed. Received April 1, 1997, and in revised form June 20, 1997.     

Minimality and unique ergodicity for adic transformations

We study the relationship between minimality and unique ergodicity for adic transformations. We show that three is the smallest alphabet size for a unimodular “adic counterexample”, an adic transformation which is minimal but not uniquely ergodic. We construct a specific family of counterexamples built from (3 × 3) nonnegative integer matrix sequences, while showing that no such (2 × 2) sequence is possible. We also consider (2 × 2) counterexamples without the unimodular restriction, describing two families of such maps. Though primitivity of the matrix sequence associated to the transformation implies minimality, the converse is false, as shown by a further example: an adic transformation with (2 × 2) stationary nonprimitive matrix, which is both minimal and uniquely ergodic.     

A mass formula for unimodular lattices with no roots

We derive a mass formula for -dimensional unimodular lattices having any prescribed root system. We use Katsurada's formula for the Fourier coefficients of Siegel Eisenstein series to compute these masses for all root systems of even unimodular 32-dimensional lattices and odd unimodular lattices of dimension . In particular, we find the mass of even unimodular 32-dimensional lattices with no roots, and the mass of odd unimodular lattices with no roots in dimension , verifying Bacher and Venkov's enumerations in dimensions 27 and 28. We also compute better lower bounds on the number of inequivalent unimodular lattices in dimensions 26 to 30 than those afforded by the Minkowski-Siegel mass constants.

     

Doi-Hopf modules, Yetter-Drinfel'd modules and Frobenius type properties

We study the following question: when is the right adjoint of the forgetful functor from the category of -Doi-Hopf modules to the category of -modules also a left adjoint? We can give some necessary and sufficient conditions; one of the equivalent conditions is that and the smash product are isomorphic as -bimodules. The isomorphism can be described using a generalized type of integral. Our results may be applied to some specific cases. In particular, we study the case , and this leads to the notion of -Frobenius -module coalgebra. In the special case of Yetter-Drinfel'd modules over a field, the right adjoint is also a left adjoint of the forgetful functor if and only if is finite dimensional and unimodular.

     

The satisfactory partition problem

The SATISFACTORY PARTITION problem consists in deciding if a given graph has a partition of its vertex set into two nonempty parts such that each vertex has at least as many neighbors in its part as in the other part. This problem was introduced by Gerber and Kobler [Partitioning a graph to satisfy all vertices, Technical report, Swiss Federal Institute of Technology, Lausanne, 1998; Algorithmic approach to the satisfactory graph partitioning problem, European J. Oper. Res. 125 (2000) 283-291] and further studied by other authors but its complexity remained open until now. We prove in this paper that SATISFACTORY PARTITION, as well as a variant where the parts are required to be of the same cardinality, are NP-complete. However, for graphs with maximum degree at most 4 the problem is polynomially solvable. We also study generalizations and variants of this problem where a partition into k nonempty parts (k?3) is requested.     

The KP hierarchy, branched covers, and triangulations

The KP hierarchy is a completely integrable system of quadratic, partial differential equations that generalizes the KdV hierarchy. A linear combination of Schur functions is a solution to the KP hierarchy if and only if its coefficients satisfy the Plücker relations from geometry. We give a solution to the Plücker relations involving products of variables marking contents for a partition, and thus give a new proof of a content product solution to the KP hierarchy, previously given by Orlov and Shcherbin. In our main result, we specialize this content product solution to prove that the generating series for a general class of transitive ordered factorizations in the symmetric group satisfies the KP hierarchy. These factorizations appear in geometry as encodings of branched covers, and thus by specializing our transitive factorization result, we are able to prove that the generating series for two classes of branched covers satisfies the KP hierarchy. For the first of these, the double Hurwitz series, this result has been previously given by Okounkov. The second of these, that we call the m-hypermap series, contains the double Hurwitz series polynomially, as the leading coefficient in m. The m-hypermap series also specializes further, first to the series for hypermaps and then to the series for maps, both in an orientable surface. For the latter series, we apply one of the KP equations to obtain a new and remarkably simple recurrence for triangulations in a surface of given genus, with a given number of faces. This recurrence leads to explicit asymptotics for the number of triangulations with given genus and number of faces, in recent work by Bender, Gao and Richmond.     

Unimodular graphs and Eisenstein sums

Motivated in part by combinatorial applications to certain sum-product phenomena, we introduce unimodular graphs over finite fields and, more generally, over finite valuation rings. We compute the spectrum of the unimodular graphs, by using Eisenstein sums associated with unramified extensions of such rings. We derive an estimate for the number of solutions to the restricted dot product equation \(a\cdot b=r\) over a finite valuation ring. Furthermore, our spectral analysis leads to the exact value of the isoperimetric constant for half of the unimodular graphs. We also compute the spectrum of Platonic graphs over finite valuation rings, and products of such rings—e.g., \(\mathbb {Z}/(N)\). In particular, we deduce an improved lower bound for the isoperimetric constant of the Platonic graph over \(\mathbb {Z}/(N)\).     

Rationally but not integrally isometric bilinear forms

Let K be a non-dyadic local field and A its ring of integers. First we notice that the classification of unimodular A-bilinear forms and of systems of two unimodular symmetric A-bilinear forms are both reduced to the classification of hermitian forms over the category of double isomorphisms over projective A-modules ; the duality is nevertheless different for each case. Then we use the methods of reduction and transfer to construct some examples of non isometric unimodular forms (or system of unimodular symmetric forms) having the same asymmetry and becoming isometric over K.     

On an Ideal in Algebras of Unbounded Operators

The closure of the set of finite dimensional operators of ??⁺?? with respect to different topologies is considered. The obtained ideals have many properties similar to those of the ideal of completely continuous operators on HILBERT space. For example, under some appropriate assumptions all continuous functionals are normal, irreducible representations are equivalent to the identical representation and so on.     

A full characterization of invariant embeddability of unimodular planar graphs

When can a unimodular random planar graph be drawn in the Euclidean or the hyperbolic plane in a way that the distribution of the random drawing is isometry-invariant? This question was answered for one-ended unimodular graphs in Benjamini and Timar, using the fact that such graphs automatically have locally finite (simply connected) drawings into the plane. For the case of graphs with multiple ends the question was left open. We revisit Halin's graph theoretic characterization of graphs that have a locally finite embedding into the plane. Then we prove that such unimodular random graphs do have a locally finite invariant embedding into the Euclidean or the hyperbolic plane, depending on whether the graph is amenable or not.     

Decision-making by hierarchies of discordant agents

We study the following decision-making scenario: A linear program is solved by a set of agents arranged hierarchically in a tree, where each agent decides the level of certain variables, and has a distinct objective function, known to all agents. Authority is reflected in two ways: Agents higher in the tree set their variables first; and agents that are siblings in the tree resolve their game by focusing on the Nash equilibrium that is optimum for the agent above them. We give a necessary and sufficient condition for such a hierarchy to be efficient (i.e., to have perfect coordination, to ultimately optimize the objective of the firm). We study problems related to designing a hierarchy (assigning decision makers to positions in the tree) in order to achieve efficiency or otherwise optimize coordination. Received June 16, 1997 / Revised version received July 8, 1998?Published online May 12, 1999     

Matrix fractions and full system equivalence

Following the definition by Hayton et al. (1990) of full systemequivalence for linear multivariables systems, the concept offull unimodular equivalence is defined for matrix fraction descriotions(MFDs).Full unimodular equivalence is an extension of unimodular equivalence,which has been proposed by Kailath (1980) and Smith (1981) forsystems described by polynomial matrix models in either leftor right MFD form. Full unimodular equivalence has the propertyof leaving invariant both the finite and infinite structureof the system. It is shown that full unimodular equivalencefor MFDs and full system equivalence coincide.     

Decomposition of Matrices into Involutory Matrices and Symmetric Matrices

Let \Omega be a field, and let F denote the Frobenius matrix: $[F = \left( {\begin{array}{*{20}{c}} 0&{ - {\alpha _n}}\{{E_{n - 1}}}&\alpha \end{array}} \right)\]$ where \alpha is an n-1 dimentional vector over Q, and E_n- 1 is identity matrix over \Omega. Theorem 1. There hold two elementary decompositions of Frobenius matrix: (i) F=SJB, where S, J are two symmetric matrices, and B is an involutory matrix; (ii) F=CQD, where O is an involutory matrix, Q is an orthogonal matrix over \Omega, and D is a diagonal matrix. We use the decomposition (i) to deduce the following two theorems: Theorem 2. Every square matrix over \Omega is a product of twe symmetric matrices and one involutory matrix. Theorem 3. Every square matrix over \Omega is a product of not more than four symmetric matrices. By using the decomposition (ii), we easily verify the following Theorem 4(Wonenburger-Djokovic') . The necessary and sufficient condition that a square matrix A may be decomposed as a product of two involutory matrices is that A is nonsingular and similar to its inverse A^-1 over Q (See [2, 3]). We also use the decomosition (ii) to obtain Theorem 5. Every unimodular matrix is similar to the matrix CQB, where C, B are two involutory matrices, and Q is an orthogonal matrix over Q. As a consequence of Theorem 5. we deduce immediately the following Theorem 6 (Gustafson-Halmos-Radjavi). Every unimodular matrix may be decomposed as a product of not more than four involutory matrices (See [1] ). Finally, we use the decomposition (ii) to derive the following Thoerem 7. If the unimodular matrix A possesses one invariant factor which is not constant polynomial, or the determinant of the unimodular matrix A is I and A possesses two invariant factors with the same degree (>0), then A may be decomposed as a product of three involutory matrices. All of the proofs of the above theorems are constructive.     

Strong conical hull intersection property, bounded linear regularity, Jameson’s property (G), and error bounds in convex optimization

The strong conical hull intersection property and bounded linear regularity are properties of a collection of finitely many closed convex intersecting sets in Euclidean space. These fundamental notions occur in various branches of convex optimization (constrained approximation, convex feasibility problems, linear inequalities, for instance). It is shown that the standard constraint qualification from convex analysis implies bounded linear regularity, which in turn yields the strong conical hull intersection property. Jameson’s duality for two cones, which relates bounded linear regularity to property (G), is re-derived and refined. For polyhedral cones, a statement dual to Hoffman’s error bound result is obtained. A sharpening of a result on error bounds for convex inequalities by Auslender and Crouzeix is presented. Finally, for two subspaces, property (G) is quantified by the angle between the subspaces. Received October 1, 1997 / Revised version received July 21, 1998? Published online June 11, 1999     

Konvergenz in verallgemeinerten topologischen Räumen

Spline – projectors in BANACH spaces. A class of BANACH spaces is studied in which it is possible to construct explicitly spline – projectors. These projectors do not depend on the special HILBERT structure that is used for construction; therefore they are unique determined.     

Even Unimodular Gaussian Lattices of Rank 12

We classify even unimodular Gaussian lattices of rank 12, that is, even unimodular integral lattices of rank 12 over the ring of Gaussian integers. This is equivalent to the classification of the automorphisms τ with τ²=−1 in the automorphism groups of all the Niemeier lattices, which are even unimodular (real) integral lattices of rank 24. There are 28 even unimodular Gaussian lattices of rank 12 up to equivalence.     

Cone convexity,cone extreme points,and nondominated solutions in decision problems with multiobjectives

Although there is no universally accepted solution concept for decision problems with multiple noncommensurable objectives, one would agree that agood solution must not be dominated by the other feasible alternatives. Here, we propose a structure of domination over the objective space and explore the geometry of the set of all nondominated solutions. Two methods for locating the set of all nondominated solutions through ordinary mathematical programming are introduced. In order to achieve our main results, we have introduced the new concepts of cone convexity and cone extreme point, and we have explored their main properties. Some relevant results on polar cones and polyhedral cones are also derived. Throughout the paper, we also pay attention to an important special case of nondominated solutions, that is, Pareto-optimal solutions. The geometry of the set of all Pareto solutions and methods for locating it are also studied. At the end, we provide an example to show how we can locate the set of all nondominated solutions through a derived decomposition theorem.