Connectedness, classes, and cycle index
CORR 1996-20
E.A. Bender, P.J. Cameron, A.M. Odlyzko and L.B. Richmond
Abstract
This paper begins with the observation that half of all graphs containing no induced path of length 3 are disconnected. We generalize this in several directions. First, we give necessary and sufficient conditions (in terms of generating functions) for the probability of connectedness in a suitable class of graphs to tend to a limit strictly between zero and one. Next we give a general framework in which this and related questions can be posed, involving operations on classes of finite structures. Finally, we discuss briefly an algebra associated with such a class of structures, and give a conjecture about its structure.
An elementary introduction to hyperelliptic curves
CORR 1996-19
Alfred J. Menezes, Yi-Hong Wu and Robert J. Zuccherato
Abstract
This paper presents an elementary introduction to some of the theory of hyperelliptic curves over finite fields of arbitrary characteristic that has cryptographic relevance. Cantor's algorithm for adding in the jacobian of a hyperelliptic curve and a proof of correctness of the algorithm are presented.
Primal-Dual Symmetry and Scale Invariance of Interior-Point Algorithms for Convex Optimization
CORR 1996-18
Levent Tunçel
Abstract
We present a definition of symmetric primal-dual algorithms for convex optimization problems expressed in the conic form. After describing a generalization of the \(v\)-space approach for such optimization problems, we show that a symmetric \(v\)-space approach can be developed for a convex optimization problem in the conic form if and only if the underlying cone is homogeneous and self-dual. We provide an alternative definition of self-scaled barriers and then conclude with a discussion of the scalings of the variables which keep the underlying convex cone invariant. Numerical results illustrate the efficacy of the SDP relaxations.
Semidefinite Programming Relaxations for the Graph Partitioning Problem
CORR 1996-17
Henry Wolkowicz and Qing Zhao
Abstract
A semidefinite programming, SDP, relaxation for the graph partitioning problem, GP, is derived using the dual of the (homogenized) Lagrangian dual of appropriate equivalent representations of GP. The special strcture of the relaxation is exploited in order to project the SDP onto the minimal face, of the cone of positive semidefinite matrices, which contains the feasible set. This guarantees that the Slater constraint qualification holds; which allows for a primal-dual interior-point solution technique. A gangster operator is the key to providing an efficient representation of the constraints. An incomplete preconditioned conjugate gradient method is used for solving the larger linear systems which arise when finding the Newton direction.
Numerical results illustrate the efficacy of the SDP relaxations.
Principally unimodular skew-symmetric matrices
CORR 1996-16
Andre Bouchet, W.H. Cunningham and J.F. Geelen
Abstract
A square matrix is principally unimodular if every principal submatrix has determinant 0 or \(\pm\) 1. Let \(\pm\) be a symmetric $(0,1)-matrix, with a zero diagonal. A PU-orientation of \(A\) is a skew-symmetric signing of \(A\) that is PU. If \(A\) is a PU-orientation of \(A\), then, by a certain decomposition of \(A\), we can construct every PU-orientation of \(A\)jj from \(A'\). This construction is based on the fact that the PU-orientations of indecomposable matrices are unique up to negation and multiplication of certain rows and corresponding columns by \(-1\). This generalizes the well-known result of Camion, that if a \((0,1)\)-matrix can be signed to be totally unimodular then the signing is unique up to multiplying certain rows and columns by \(-1\). Camion's result is an easy but crucial step in proving Tutte's famous excluded minor characterization of totally unimodular matrices.
Nonsmooth analysis of eigenvalues
CORR 1996-15
A.S. Lewis
Abstract
The eigenvalues of a symmetric matrix depend on the matrix nonsmoothly. This paper describes the nonsmooth analysis of these eigenvalues. In particular, I present a simple formula for the approximate (limiting Frechet) subdifferential of an arbitrary function of the eigenvalues, subsuming earlier results on convex and Clarke subgradients. As an example I compute the subdifferential of the \(k \)'th largest eigenvalue.
The virtual Euler characteristic of the moduli spaces of real and complex algebraic curves
CORR 1996-14
I.P. Goulden, J.L. Harer and D.M. Jackson
Abstract
We determine the virtual Euler characteristics of the moduli spaces of \(s
\)-pointed real and complex algebraic curves. In particular, for the space of real curves of genus \(g\) with a fixed point free in involution, we find that the Euler characteristic is \((-2)^{s-1}(1-2^{g-1})g+s-2)!B_g/g!\) where \(B_g\) is the \(g\)th Bernoulli number. This complements the result of Harer and Zagier that the Euler characteristic of the moduli space of complex algebraic curves is \((-1)^s(g+s-2)!B_{g+1}/(g+1)(g-1)!\)
The proof uses Strebel differentials to triangulate the moduli spaces and some recent enumerative techniques to count cells. The approach involves a parameter that permits specialization of the formula to the real and complex cases. This suggests that the general expression itself may describe the Euler characteristics of some related moduli spaces, although we do not yet know what these spaces might be.
Zero-One Laws for Maps
CORR 1996-13
Edward A. Bender, Kevin J. Compton and L. Bruce Richmond
Abstract
A class of finite structures has 0-1 law with respect to a logic if every property expressible in the logic has a probability approaching a limit of 0 or 1 as the structure size grows. To formulate 0-1 laws for maps (i.e., embeddings of graphs in a surface), it is necessary to represent maps as logical structures. Three such representations are given, the most general being the full cross representation based on Tutte's theory of combinatorial maps. The main result says that if a class of maps has two properties, richness and large representativity, then the corresponding class of full cross representations has a 0-1 law with respect to first-order logic. As a corollary the following classes of maps on a surface of fixed type have a first-order 0-1 law: all maps, smooth maps, 2-connected maps, 3-connected maps, triangular maps, 2-connected triangular maps, and 3-connected triangular maps.
A Decomposition Procedure for Global and Local Quadratic Minimization
CORR 1996-12
M.J. Best and B. Ding
Abstract
We present a decomposition method which, when applied to certain nonconvex QP will locate the global minimum, all isolated local minima and some of the nonisolated local minima. The method proceeds by formulating a (multi) parametric LP in terms of the data of the given nonconvex QP. We use this and a decomposition procedure to transform the given $n$ dimensional nonconvex QP having \(m\) linear inequality constraints into \(k\) subproblem QP's, each of which has \(n-1\) variables and \(m\) constraints, where \(1 \leq k \leq m\) and $k$ depends on the problem data. Special techniques are developed to ensure that \(k\) is small. The decomposition procedure may then be applied to the subproblem QP's. A branch of decomposition procdure terminates when either the subproblem is concave or the subproblem has a Hessian matrix having exactly one negative eigenvalue or the subproblem has dimension 1. Numerical examples are given to illustrate the central concepts.
Zeros of reliability polynomials and f-vectors of matroids
CORR 1996-11
David G. Wagner
Abstract
For a finite multigraph \(G\), the reliability function of \(G\) is the probability \(R_{G}(q)\) that if each edge of \(G\) is deleted independently with probability \(q\) then the remaining edges of \(G\) induce a connected spanning subgraph of $G$; this is a polynomial function of \(q\). In 1992, Brown and Colbourn conjectured that for any connected multigraph \(G\), if \(q \in {\cal C}\) is such that \(R_{G}(q) = 0\) then \(|q| \leq 1\). We verify that this conjectured property of \(R_{G}(q)\) holds if \(G\) is a series-parallel network. The proof is by an application of the Hermite-Biehler Theorem and development of a theory of higher-order interlacing for polynomials with only real nonpositive zeros. We conclude by establishing some new inequalities which are satisfied by the \(f\)-vector of any matroid without coloops, and by discussing some stronger inequalities which would follow (in the cographic case) from the Brown-Colbourn Conjecture, and are hence true for cographic matroids of series-parallel networks.
Wheel Inequalities for Stable Set Polytopes
CORR 1996-10
Eddie Cheng and William H. Cunningham
Abstract
We introduce new classes of valid inequalities, called wheel inequalities, for the stable set polytope \(P_G\) of a graph $G$. Each "wheel configuration" gives rise to two such inequalities. The simplest wheel configuration is an "odd" subdivision \(W\) of a wheel, and for these we give necessary and sufficient conditions for the wheel inequality to be facet-inducing for \(P_W\). Generalizations arise by allowing subdivision paths to intersect, and by replacing the "hub" of the wheel by a clique. The separation problem for these inequalities can be solved in polynomial time.
Filters of the Boolean Algebra having the LYM property
CORR 1996-09
David G.C. Horrocks
Abstract
For a nonempty collection {\cal F} of subsets, each having cardinality 2, of \([n]={1,2,...,n}\), let \(P_{\cal F}\) be the poset consisting of all subsets of \([n]\) which contain at least one member of {\cal F}, ordered by inclusion. We describe a general procedure for showing that {\cal F} has the LYM property and then use the method to construct several examples. Finally, we discuss the application of the results to a conjecture of Lih, which states that \(P_{\cal F}\) has the Sperner property for every collection {\cal F} of 2-subsets.
Admissible Functions and Asymptotics for Labelled Structures by Number of Components
CORR 1996-08
Edward A. Bender and L. Bruce Richmond
Abstract
Let $a(n,k)$ denote the number of combinatorial structures of size \(n\) with \(k \) components. Often\(\sum_{n,k} a(n,k)x^{n}y^{k}/n! = exp{yC(x)}\), where \(C(x)\) is the exponential generating function for connected structures. How does \(a(n,k)\) behave as a function of \(k\) when \(n\) is large and \(C(x)\) is entire or has large singularities on its circle of convergence? The Flajolet-Odlyzko singularity analysis does not directly apply in such cases. We extend some of Hayman's work on admissible functions of a single variable to functions of several variables. As applications, we obtain asymptotics and local limit theorems for several set partition problems, decomposition of vector spaces, tagged permutations, and various complete graph covering problems.
A Constant-Potential Infeasible-Start Interior-Point Algorithm with Computational Experiments and Applications
CORR 1996-07
Abbas Seifi and Levent Tunçel
Abstract
We present a constant-potential infeasible-start interior-point (INFCP) algorithm for linear programming (LP) problems with a worst-case iteration complexity analysis as well as some computational results. The performance of the INFCP algorithm is compared to those of practical interior-point algorithms. New features of the algorithm include a heuristic method for computing a "good" starting point and a procedure for solving the augmented systems arising from stochastic programming with recourse. We also present an application to large scale linear programming problems arising from planning under uncertainity.
Integral Solutions of Linear Complementarity Problems
CORR 1996-06
William H. Cunningham and James F. Geelen
Abstract
We characterize the class of integral square matrices $\(M\)$ having the property that for every integral vector \(q\) the linear complementarity problem with data \(M,q\) has only integral basic solutions. These matrices, called principally unimodular matrices, are those for which every principal nonsingular submatrix is unimodular. As a consequence, we show that if \(M\) is rank-symmetric and principally unimodular, and \(q\) is integral, then the problem has an integral solution if it has a solution. Principal unimodularity can be regarded as an extension of total unimodularity, and our results can be regarded as extensions of well-known results on integral solutions to linear programs. We summarize what is known about principally unimodular symmetric and skew-symmetric matrices.
A Robinson-Schensted algorithm for a class of partial orders
CORR 1996-05
Thomas S. Sundquist*, David G. Wagner and Julian West
Abstract
Let \(P\) be a finite partial order which does not contain an induced subposet isomorphic with \(3+1\), and let \(G\) be the incomparability graph of \(P\). Gasharov has shown that the chromatic symmetric function \(X_G\) has nonnegative coefficients when expanded in terms of Schur functions; his proof uses the dual Jacobi-Trudi identity and a sign-reversing involution to interpret these coefficients as numbers of \(P\)-tableau. This suggests the possibility of a direct bijective proof of this result, generalizing the Robinson-Schensted correspondence. We provide such an algorithm here under the additional hypothesis that \(P\)does not contain an induced subposet isomorphic with \(\{ x>ay \\)}.
Even Directed Cycles in H-Free Digraphs
CORR 1996-04
Anna Galluccio and Martin Loebl
Abstract
A digraph is \(H\)-free if its underlying graph does not contain a subgraph contractible to the graph \(H\). We provide a polynomial-time algorithm to solve the Even Cycle Problem in the class of \(K_{3,3}\)-free digraphs and in the class of \(K_{5}\)-free digraphs. We also discuss the important role played by the subdivisions of\(K_{3,3}\) in solving the Even Cycle Problem in its generality.
Even Cycles and Backward Paths
CORR 1996-03
Anna Galluccio and Martin Loebl
Abstract
The aim of this paper is to reduce the Even Cycle Problem to the \(H\)-homeomorphism Problem. As a consequence, we present a polynomial-time algorithm to solve the Even Cycle Problem in any class of digraphs which may be drawn on a fixed but arbitrary surface. The same results hold for more general modularity problems.
On Bases of Circuit Lattices
CORR 1996-02
Winfried Hochstattler and Martin Loebl
Abstract
Our aim is to propose and study the following conjecture.
There exists a set of cycles of each binary matroid \(B\), which form a basis of the lattice generated by the ciruits of \(B\).
(P,Q)-ODD Digraphs
CORR 1996-01
A. Galluccio and M. Loebl
Abstract
A digraph \(D\) is \(D\)-odd if and only if any subdivision of \(D\) contains a directed cycle of length different from \(p mod q\). A characterization of (p,q)-odd digraphs analogous to the Seymour-Thomassen characterization of (1,2)-odd digraphs is provided.
In order to obtain this characterization we study the integer lattice generated by the directed cycles of a strongly connected digraph. We show that the sets of directed cycles obtained from an ear decomposition of the digraph in a natural way are bases of this lattice. A similar result does not hold for undirected graphs. However we constrct, for each undirected 2-connected graph \(G\), a set of cycles of \(G\) which form a basis of the integer lattice generated by the cylces of \(G\).