Generalized resolution and cutting planes

This paper illustrates how the application of integer programming to logic can reveal parallels between logic and mathematics and lead to new algorithms for inference in knowledge-based systems. If logical clauses (stating that at least one of a set of literals is true) are written as inequalities, then the resolvent of two clauses corresponds to a certain cutting plane in integer programming. By properly enlarging the class of cutting planes to cover clauses that state that at least a specified number of literals are true, we obtain a generalization of resolution that involves both cancellation-type and circulant-type sums. We show its completeness by proving that it generates all prime implications, generalizing an early result by Quine. This leads to a cutting-plane algorithm as well as a generalized resolution algorithm for checking whether a set of propositions, perhaps representing a knowledge base, logically implies a given proposition. The paper is intended to be readable by persons with either an operations research or an artificial intelligence background.This report was prepared as part of the activities of the Management Sciences Research Group, Carnegie-Mellon University. Reproduction in whole or in part is permitted for any purpose of the U.S. Government.     

Equivariant embeddings of low dimensional symmetric planes

We determine the class of all locally compact stable planesM of positive dimensiond4 which admit a reflection at each point of some open setU M. Apart from the expected possibilities (planes defined by real and complex hermitian forms, and almost projective translation planes), one obtains (subplanes of)H. Salzmann's modified real hyperbolic planes [14; 5.3] and one exceptional plane which was not known before. The caseU=M has been treated [9] and is reproved here in a simpler way. The solution to the problem indicated in the title constitutes the main step in the proof of our results.     

On symmetric incidence matrices of projective planes

We investigate the incidence matrix of a finite plane of ordern which admits a (C, L)-transitivityG. The elation groupG affords a generalized Hadamard matrixH=(h _ij ) of ordern and an incidence matrix for the plane is completely determined by the matrixR(H)=(R(h _ij )), whereR(g) denotes the regular permutation matrix forgG. We prove that in the caseR(H) is symmetric thatG is an elementary abelian 2-group or elseG is a nonabelian group andn is a square. Results are obtained in the abelian case linking the roots of the incidence matrixR(H) to the roots of the complex matrix (H), a nontrivial character ofG.     

Generalized weakly symmetric rings

A ring R is defined to be GWS   if abc=0$abc=0$ implies bac⊆N(R)$bac\subseteq N(R)$ for a,b,c∈R$a,b,c\in R$, where N(R)$N(R)$ stands for the set of nilpotent elements of R. Since reduced rings and central symmetric rings are GWS, we study sufficient conditions for GWS rings to be reduced and central symmetric. We prove that a ring R is GWS   if and only if the n×n$n\times n$ upper triangular matrices ring _Un(R,R)$U_n(R,R)$ is GWS for any positive integer n. It is proven that GWS rings are directly finite and left min-abel. For a GWS ring R, R is a strongly regular ring if and only if R is a von Neumann regular ring if and only if R is a left SF   ring and J(R)=0$J(R)=0$; R is an exchange ring if and only if R is a clean ring. Finally, we show that GWS exchange rings have stable range 1 and a GWS semiperiodic ring R   with N(R)≠J(R)$N(R)\ne J(R)$ is commutative.     

Generalized symplectic symmetric spaces

Bieliavsky introduced and investigated a class of symplectic symmetric spaces, that is, symmetric spaces endowed with a symplectic structure invariant with respect to symmetries. The theory of symmetric spaces has essential and interesting generalizations due to the fundamental work of Gray and Wolf continued by many researchers. Therefore, we ask a question about possible symplectic versions of such theory. In this paper we do obtain such generalization, and, in particular, give a list of all symplectic 3-symmetric manifolds with simple groups of transvections. We also show a method of constructing semisimple (noncompact) symplectic \(k\) -symmetric spaces from a given (compact) Kähler k-symmetric space.     

Generalized quadrangles constructed from topological Laguerre planes

The Lie geometry of a finite-dimensional locally compact connected Laguerre plane is a topological generalized quadrangle.     

Generalized power symmetric stochastic matrices

We characterize stochastic matrices which satisfy the equation where are positive integers.

     

Generalized blocks for symmetric groups

We study, via character-theoretic methods, an ℓ-analogue of the modular representation theory of the symmetric group, for an arbitrary integer ℓ≥2. We find that many of the invariants of the usual block theory (ie. when ℓ is prime) generalize in a natural fashion to this new context. Oblatum 21-III-2002 & 5-VIII-2002?Published online: 8 November 2002     

Intersecting all edges of centrally symmetric polyhedra by planes

A1 least three planes are needed in order to cut all edges of a 3-dimensional centrally symmetric convex polytope by planes which miss all vertices of the polytope. In contrast, there exist centrally symmetric convex tessellations of the 2-sphere for which two planes are sufficient.     

Characterization of symmetric planes in dimension at most 4

A stable plane is a topological geometry with the properties that (i) any two points are joined by a unique line, and (ii) the operations of join and intersection are continuous and have open domains of definition. A stable plane is called symmetric if its point space is a (differentiable) symmetric space whose symmetries are automorphisms of the plane.Among locally compact stable planes of positive (topological) dimension ≦ 4, we determine those which admit a reflection at each point (i.e., an involutory automorphism fixing this point line-wise), and we list the possible groups containing reflections at all points. Together with an additional, purely geometric condition, this yields a characterization of symmetric planes and, indirectly, of the plane geometries defined by real and complex hermitian forms. No differentiability hypotheses and no algebraic axioms ruling the reflections are needed.     

Generalized characters of the symmetric group

Normalized irreducible characters of the symmetric group S(n) can be understood as zonal spherical functions of the Gelfand pair (S(n)×S(n),diagS(n)). They form an orthogonal basis in the space of the functions on the group S(n) invariant with respect to conjugations by S(n). In this paper we consider a different Gelfand pair connected with the symmetric group, that is an “unbalanced” Gelfand pair (S(n)×S(n−1),diagS(n−1)). Zonal spherical functions of this Gelfand pair form an orthogonal basis in a larger space of functions on S(n), namely in the space of functions invariant with respect to conjugations by S(n−1). We refer to these zonal spherical functions as normalized generalized characters of S(n). The main discovery of the present paper is that these generalized characters can be computed on the same level as the irreducible characters of the symmetric group. The paper gives a Murnaghan-Nakayama type rule, a Frobenius type formula, and an analogue of the determinantal formula for the generalized characters of S(n).     

Using cutting planes to solve the symmetric Travelling Salesman problem

Two algorithms using cutting planes are developed for solving the Travelling Salesman Problem. In both algorithms the problem is started with a subset of the set of constraints that define the problem (apart from integrality requirements).However, the two algorithms differ in the order in which the omitted constraints and the cutting planes that are required are generated.The computational experience obtained suggests that cutting planes can provide a competitive approach to other efficient methods of solving the problem.     

Generalized symmetric functions and invariants of matrices

We generalize the classical isomorphism between symmetric functions and invariants of a matrix. In particular, we show that the invariants over several matrices are given by the abelianization of the symmetric tensors over the free associative algebra. The main result is proved by finding a characteristic free presentation of the algebra of symmetric tensors over a free algebra. The author is supported by research grant Politecnico di Torino n.119, 2004.     

Generalized symmetric ADMM for separable convex optimization

The alternating direction method of multipliers (ADMM) has been proved to be effective for solving separable convex optimization subject to linear constraints. In this paper, we propose a generalized symmetric ADMM (GS-ADMM), which updates the Lagrange multiplier twice with suitable stepsizes, to solve the multi-block separable convex programming. This GS-ADMM partitions the data into two group variables so that one group consists of p block variables while the other has q block variables, where \(p \ge 1\) and \(q \ge 1\) are two integers. The two grouped variables are updated in a Gauss–Seidel scheme, while the variables within each group are updated in a Jacobi scheme, which would make it very attractive for a big data setting. By adding proper proximal terms to the subproblems, we specify the domain of the stepsizes to guarantee that GS-ADMM is globally convergent with a worst-case \({\mathcal {O}}(1/t)\) ergodic convergence rate. It turns out that our convergence domain of the stepsizes is significantly larger than other convergence domains in the literature. Hence, the GS-ADMM is more flexible and attractive on choosing and using larger stepsizes of the dual variable. Besides, two special cases of GS-ADMM, which allows using zero penalty terms, are also discussed and analyzed. Compared with several state-of-the-art methods, preliminary numerical experiments on solving a sparse matrix minimization problem in the statistical learning show that our proposed method is effective and promising.