Optimum matching forests II: General weights

Matching forests generalize branchings in a directed graph and matchings in an undirected graph. We present an efficient algorithm, the PMF Algorithm, for the problem: given a mixed graphG and a real weight on each of its edges, find a perfect matching forest of maximum weight-sum. The PMF Algorithm proves the sufficiency of a linear system which definesP ⁼ (G) andP(G), the convex hull of incidence vectors of perfect matching forests and matching forests respectively ofG. The algorithm also provides a generalization of Tutte's theorem on the existence of perfect matchings in an undirected graph.Research partially supported by a N.R.C. of Canada Postdoctorate Fellowship.     

Facets of the balanced (acyclic) induced subgraph polytope

A signed graph is a graph whose edges are labelled positive or negative. A signed graph is said to be balanced if the set of negative edges form a cut. The balanced induced subgraph polytopeP(G) of a graphG is the convex hull of the incidence vectors of all node sets that induce balanced subgraphs ofG. In this paper we exhibit various (rank) facet defining inequalities. We describe several methods with which new facet defining inequalities ofP(G) can be constructed from known ones. Finding a maximum weighted balanced induced subgraph of a series parallel graph is a polynomial problem. We show that for this class of graphsP(G) may have complicated facet defining inequalities. We derive analogous results for the polytope of acyclic induced subgraphs.Research supported in part by the Natural Sciences and Engineering Research Council of Canada; the second author has also been supported by C.P. Rail.     

On the monotonization of polyhedra

In polyhedral combinatorics one often has to analyze the facial structure of less than full dimensional polyhedra. The presence of implicit or explicit equations in the linear system defining such a polyhedron leads to technical difficulties when analyzing its facial structure. It is therefore customary to approach the study of such a polytopeP through the study of one of its (full dimensional) relaxations (monotonizations) known as the submissive and the dominant ofP. Finding sufficient conditions for an inequality that induces a facet of the submissive or the dominant of a polyhedron to also induce a facet of the polyhedron itself has been posed in the literature as an important research problem. Our paper goes a long way towards solving this problem. We address the problem in the framework of a generalized monotonization of a polyhedronP, g-mon(P), that subsumes both the submissive and the dominant, and give a sufficient condition for an inequality that defines a facet of g-mon(P) to define a facet ofP. For the important cases of the traveling salesman (TS) polytope in both its symmetric and asymmetric variants, and of the linear ordering polytope, we give sufficient conditions trivially easy to verify, for a facet of the monotone completion to define a facet of the original polytope itself. Research supported by grant DMI-9201340 of the National Science Foundation and contract N00014-89-J-1063 of the Office of Naval Research. Research supported by MURST, Italy.     

The perfectly Matchable Subgraph Polytope of an arbitrary graph

The Perfectly Matchable Subgraph Polytope of a graphG=(V, E), denoted byPMS(G), is the convex hull of the incidence vectors of thoseXV which induce a subgraph having a perfect matching. We describe a linear system whose solution set isPMS(G), for a general (nonbipartite) graphG. We show how it can be derived via a projection technique from Edmonds' characterization of the matching polytope ofG. We also show that this system can be deduced from the earlier bipartite case [2], by using the Edmonds-Gallai structure theorem. Finally, we characterize which inequalities are facet inducing forPMS(G), and hence essential.     

Thed-step conjecture for polyhedra of dimensiond<6

Two functions Δ and Δ _b , of interest in combinatorial geometry and the theory of linear programming, are defined and studied. Δ(d, n) is the maximum diameter of convex polyhedra of dimensiond withn faces of dimensiond−1; similarly, Δ _b (d,n) is the maximum diameter of bounded polyhedra of dimensiond withn faces of dimensiond−1. The diameter of a polyhedronP is the smallest integerl such that any two vertices ofP can be joined by a path ofl or fewer edges ofP. It is shown that the boundedd-step conjecture, i.e. Δ _b (d,2d)=d, is true ford≤5. It is also shown that the generald-step conjecture, i.e. Δ(d, 2d)≤d, of significance in linear programming, is false ford≥4. A number of other specific values and bounds for Δ and Δ _b are presented. This revised version was published online in November 2006 with corrections to the Cover Date.     

The graphical relaxation: A new framework for the symmetric traveling salesman polytope

A present trend in the study of theSymmetric Traveling Salesman Polytope (STSP(n)) is to use, as a relaxation of the polytope, thegraphical relaxation (GTSP(n)) rather than the traditionalmonotone relaxation which seems to have attained its limits. In this paper, we show the very close relationship between STSP(n) and GTSP(n). In particular, we prove that every non-trivial facet of STSP(n) is the intersection ofn + 1 facets of GTSP(n),n of which are defined by the degree inequalities. This fact permits us to define a standard form for the facet-defining inequalities for STSP(n), that we calltight triangular, and to devise a proof technique that can be used to show that many known facet-defining inequalities for GTSP(n) define also facets of STSP(n). In addition, we give conditions that permit to obtain facet-defining inequalities by composition of facet-defining inequalities for STSP(n) and general lifting theorems to derive facet-defining inequalities for STSP(n +k) from inequalities defining facets of STSP(n).Partially financed by P.R.C. Mathématique et Informatique.     

Computing low-capacity 0–1 knapsack polytopes

A procedure is proposed that, given a linear inequalityL having positive integral coefficients in 0–1 variables, finds all the facets of the convex hull of the solutions ofL. This is done for allL by doing once and for all the computations for a particular sequenceM ₁,M ₂,... of such linear inequalities, called master knapsack problems. To find the facets for a givenL, it is enough to know the facets for the master knapsack problemM _b, whereb is the free term inL (no matter how many variablesL might have). ThisM _b has no more than order ofb logb variables. The procedure is based on polarity. All the facets forM ₁,...,M ₇ are tabulated.

---

Zusammenfassung Es wird ein Verfahren vorgestellt, das für eine lineare UngleichungL in binären Variablen mit positiven ganzzahligen Koeffizienten alle Facetten der konvexen Hülle der Lösungen vonL bestimmt. Um diese Facetten für irgendeine UngleichungL mit rechter Seiteb zu erhalten, braucht man nur die Facetten des sogenannten Master-Knapsack-ProblemsM _b zu kennen, dasO (b log b) Variablen besitzt. Fürb=1,..., 7 werden alle Facetten vonM _b angegeben.

     

Continuity of operators commuting with translations for compact groups

In this note we show for certain Frechet spacesF(G) of functions (distributions) on a compact groupG that if every translation invariant linear functional onF(G) is continuous then every linear operatorT:F(G)F(G) commuting with translations is continuous. This solves partially a problem in [7] ofG. H. Meisters and improves the result [5] ofC. J. Lester. An application for compact groups which do not have the mean zero weak containment property follows by the result [10] ofG. A. Willis.     

Simulated factorizations II

Summary A factorization of a finite abelian group is said to be simulated if it is obtained from a factorization into a direct product of subgroups by changing at mostk elements in each subgroup. The question has been asked as to which values ofk imply that in fact at least one subgroup must be left unaltered. This has been shown to be true fork = 1 but to be false, in general, fork = p – 1, wherep is the least prime dividing the order ofG. In this paper it is shown to be true fork = p – 2.     

On density properties of certain subgroups with boundedness conditions

LetG be a locally compact group acting on a topological space. Here we define some boundedness conditions for the action. For a nondiscrete locally compact vector spaceV andgG L (V), layering structures forV and the projective spaceP (V) ofV are obtained. From the layering structures, we derive then density properties of subgroups ofG with boundedness conditions. We generalize the Borel density theorem and Prasad's theorem on automorphisms of algebraic semi-simple groups. Some new results onp-adic groups are added.Partially supported by N. S. F. Grant 7702168.     

Inequalities forf-vectors of 4-polytopes

LetV, E, S andF be the number of vertices, edges, subfacets and facets, respectively, of a 4-dimensional convex polytope. In this paper we derive new upper and lower bounds forS in terms ofF andV. Research supported by NSF grants GP-27963 and GP-19221.     

The expected value of some functions of the convex hull of a random set of points sampled inR d

This paper presents formulas and asymptotic expansions for the expected number of vertices and the expected volume of the convex hull of a sample ofn points taken from the uniform distribution on ad-dimensional ball. It is shown that the expected number of vertices is asymptotically proportional ton ^{(d−1)/(d+1)}, which generalizes Rényi and Sulanke’s asymptotic raten ^(1/3) ford=2 and agrees with Raynaud’s asymptotic raten ^{(d−1)/(d+1)} for the expected number of facets, as it should be, by Bárány’s result that the expected number ofs-dimensional faces has order of magnitude independent ofs. Our formulas agree with the ones Efron obtained ford=2 and 3 under more general distributions. An application is given to the estimation of the probability content of an unknown convex subset ofR ^d .     

On the number of copies of one hypergraph in another

Given two hypergraphsH andG, letN(G, H) denote the number of subhypergraphs ofG isomorphic toH. LetN(l, H) denote the maximum ofN(G, H), taken over allG with exactlyl edges. In [1] Noga Alon analyzes the asymptotic behaviour ofN(l, H) forH a graph. We generalize this to hypergraphs: Theorem:For a hypergraph H with fractional cover number ρ*,N(G,H).=θ(lρ*) The interesting part of this is the upper bound, which is shown to be a simple consequence of an entropy lemma of J. Shearer. In a special case which includes graphs, we also provide a different proof using a hypercontractive estimate. Research supported in part by NSF.     

Krull dimension and integrality of symmetric algebras

For a finitely generated moduleE over the Noetherian ringR we consider formulas for the Krull dimension of the symmetric algebraS(E). A result of Huneke and Rossi is re-proved and an effective formula is derived that reads the dimension ofS(E) from a presentation ofE. They provide a first line of obstructions forS(E) to be an integral domain. For algebras of codimension at most four we give methods, including computer-assisted ones, to ascertain whetherS(E) is a Cohen-Macaulay domain.AMS 1980 Mathematics Subject Classification (1985 Revision). Primary 13H10; Secondary 13-04, 13C05, 13C15Partially supported by CNPq, BrazilPartially supported by the NSF     

A lifting procedure for the asymmetric traveling salesman polytope and a large new class of facets

Given any family of valid inequalities for the asymmetric traveling salesman polytopeP(G) defined on the complete digraphG, we show that all members of are facet defining if the primitive members of (usually a small subclass) are. Based on this result we then introduce a general procedure for identifying new classes of facet inducing inequalities forP(G) by lifting inequalities that are facet inducing forP(G), whereG is some induced subgraph ofG. Unlike traditional lifting, where the lifted coefficients are calculated one by one and their value depends on the lifting sequence, our lifting procedure replaces nodes ofG with cliques ofG and uses closed form expressions for calculating the coefficients of the new arcs, which are sequence-independent. We also introduce a new class of facet inducing inequalities, the class of SD (source-destination) inequalities, which subsumes as special cases most known families of facet defining inequalities.Research supported by Grant DDM-8901495 of the National Science Foundation and Contract N00014-85-K-0198 of the U.S. Office of Naval Research.Research supported by M.U.R.S.T., Italy.     

A note on sufficient conditions forQ 0 andQ 0 ⋂P 0 matrices

In this note we settle an open problem posed by Al-Khayyal on a condition being sufficient for a matrix to belong to the class ofQ ₀-matrices. The answer is in the affirmative and we further relax the condition and obtain a sufficient condition forQ ₀-matrices. The results yield a class of matrices for which the linear complementarity problems can be solved as simple linear programs.     

Properties of vertex packing and independence system polyhedra

We consider two convex polyhedra related to the vertex packing problem for a finite, undirected, loopless graphG with no multiple edges. A characterization is given for the extreme points of the polyhedron \(\mathcal{L}_G = \{ x \in R^n :Ax \leqslant 1_m ,x \geqslant 0\} \) , whereA is them × n edge-vertex incidence matrix ofG and 1 _m is anm-vector of ones. A general class of facets of = convex hull{x∈R ⁿ :Ax≤1 _m ,x binary} is described which subsumes a class examined by Padberg [13]. Some of the results for are extended to a more general class of integer polyhedra obtained from independence systems.     

Conjugacy of net subgroups of linear groups

For the full linear group over a matrix-local ring whose quotient by the Jacobson radical is not the field of two elements, we settle the question of the conjugacy ofD -net subgroups (Ref. Zh. Mat., 1977, 2A280). TwoD -net subgroups are conjugate if and only if theD -nets defining them are similar (i.e., can be transformed into each other by a permutation matrix). An analogous result is obtained forD -net subgroups of the symplectic group over a commutative local ring whose residue field contains more than three elements.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 86, pp. 11–18, 1979.