Equiangular tight frames and fourth root seidel matrices

In this paper we construct complex equiangular tight frames (ETFs). In particular, we study the grammian associated with an ETF whose off-diagonal entries consist entirely of fourth roots of unity. These ETFs are classified, and we also provide some computational techniques which give rise to previously undiscovered ETFs.     

On incidence energy of a graph

The Laplacian-energy like invariant LEL(G) and the incidence energy IE(G) of a graph are recently proposed quantities, equal, respectively, to the sum of the square roots of the Laplacian eigenvalues, and the sum of the singular values of the incidence matrix of the graph G. However, IE(G) is closely related with the eigenvalues of the Laplacian and signless Laplacian matrices of G. For bipartite graphs, IE=LEL. We now point out some further relations for IE and LEL: IE can be expressed in terms of eigenvalues of the line graph, whereas LEL in terms of singular values of the incidence matrix of a directed graph. Several lower and upper bounds for IE are obtained, including those that pertain to the line graph of G. In addition, Nordhaus-Gaddum-type results for IE are established.     

Fractional perfect b-matching polytopes I: General theory

The fractional perfect b-matching polytope of an undirected graph G is the polytope of all assignments of nonnegative real numbers to the edges of G such that the sum of the numbers over all edges incident to any vertex v   is a prescribed nonnegative number _bv$b_v$. General theorems which provide conditions for nonemptiness, give a formula for the dimension, and characterize the vertices, edges and face lattices of such polytopes are obtained. Many of these results are expressed in terms of certain spanning subgraphs of G which are associated with subsets or elements of the polytope. For example, it is shown that an element u of the fractional perfect b-matching polytope of G is a vertex of the polytope if and only if each component of the graph of u either is acyclic or else contains exactly one cycle with that cycle having odd length, where the graph of u is defined to be the spanning subgraph of G whose edges are those at which u is positive.     

On dimensional rigidity of bar-and-joint frameworks

Let V={1,2,…,n}. A mapping p:V→R^r, where p¹,…,pⁿ are not contained in a proper hyper-plane is called an r-configuration. Let G=(V,E) be a simple connected graph on n vertices. Then an r-configuration p together with graph G, where adjacent vertices of G are constrained to stay the same distance apart, is called a bar-and-joint framework (or a framework) in R^r, and is denoted by G(p). In this paper we introduce the notion of dimensional rigidity of frameworks, and we study the problem of determining whether or not a given G(p) is dimensionally rigid. A given framework G(p) in R^r is said to be dimensionally rigid iff there does not exist a framework G(q) in R^s for s?r+1, such that ∥qⁱ-q^j∥²=∥pⁱ-p^j∥² for all (i,j)∈E. We present necessary and sufficient conditions for G(p) to be dimensionally rigid, and we formulate the problem of checking the validity of these conditions as a semidefinite programming (SDP) problem. The case where the points p¹,…,pⁿ of the given r-configuration are in general position, is also investigated.     

A direct proof for the matrix decomposition of chordal-structured positive semidefinite matrices

Agler, Helton, McCullough, and Rodman proved that a graph is chordal if and only if any positive semidefinite (PSD) symmetric matrix, whose nonzero entries are specified by a given graph, can be decomposed as a sum of PSD matrices corresponding to the maximal cliques. This decomposition is recently exploited to solve positive semidefinite programming efficiently. Their proof is based on a characterization for PSD matrix completion of a chordal-structured matrix due to Grone, Johnson, Sá, and Wolkowicz. This note gives a direct and simpler proof for the result of Agler et al., which leads to an alternative proof of Grone et al.     

The Gromov norm of the product of two surfaces

We make an estimation of the value of the Gromov norm of the Cartesian product of two surfaces. Our method uses a connection between these norms and the minimal size of triangulations of the products of two polygons. This allows us to prove that the Gromov norm of this product is between 32 and 52 when both factors have genus 2. The case of arbitrary genera is easy to deduce from this one.     

Displacement structure approach to q-adic polynomial-Vandermonde and related matrices

In the present paper a new class of the so-called q-adic polynomial-Vandermonde-like matrices over an arbitrary non-algebraically closed field is introduced. This class generalizes both the simple and the confluent polynomial-Vandermonde-like matrices over the complex field, and the q-adic Vandermonde and the q-adic Chebyshev-Vandermonde-like matrices studied earlier by different authors. Three kinds of displacement structures and two kinds of fast inversion formulas are obtained for this class of matrices by using displacement structure matrix method, which generalize the corresponding results of the polynomial-Vandermonde-like and the q-adic Vandermonde-like matrices.     

All 0–1 polytopes are traveling salesman polytopes

We study the facial structure of two important permutation polytopes in , theBirkhoff orassignment polytopeB _n , defined as the convex hull of alln×n permutation matrices, and theasymmetric traveling salesman polytopeT _n , defined as the convex hull of thosen×n permutation matrices corresponding ton-cycles. Using an isomorphism between the face lattice ofB _n and the lattice of elementary bipartite graphs, we show, for example, that every pair of vertices ofB _n is contained in a cubical face, showing faces ofB _n to be fairly special 0–1 polytopes. On the other hand, we show thatevery 0–1d-polytope is affinely equivalent to a face ofT _n , fordlogn, by showing that every 0–1d-polytope is affinely equivalent to the asymmetric traveling salesman polytope of some directed graph withn nodes. The latter class of polytopes is shown to have maximum diameter [n/3].Partially supported by NSF grant DMS-9207700.     

Metrics with finite sets of primitive extensions

In this paper, we give a complete characterization for the class of rational finite metrics with the property that the set () of primitive extensions of is finite. Here, for a metric on a setT, a positive extensionm of to a setV T is calledprimitive if none of the convex combinations of other extensions of toV is less than or equal tom. Our main theorem asserts that the following the properties are equivalent: (i) () is finite; (ii) Up to an integer factor, is a submetric of the path metric d ^H of a graphH with |(d ^H )=1; (iii) A certain bipartite graph associated with contains neither isometrick-cycles withk6 nor induced subgraphsK _3,3 ^– . We then show that () is finite if and only if the dimension of the tight span of is at most two. We also present other results, discuss applications to multicommodity flows, and raise open problems.This research was supported by grant 97-01-00115 from the Russian Foundation of Basic Research and a grant from the Sonderforschungsbereich 343, Bielefeld Universität, Bielefeld, Germany.     

Gröbner bases and triangulations of the second hypersimplex

The algebraic technique of Gröbner bases is applied to study triangulations of the second hypersimplex (2,n). We present a quadratic Gröbner basis for the associated toric idealK(K _n ). The simplices in the resulting triangulation of (2,n) have unit volume, and they are indexed by subgraphs which are linear thrackles [28] with respect to a circular embedding ofK _n . Forn6 the number of distinct initial ideals ofI(K _n ) exceeds the number of regular triangulations of (2,n); more precisely, the secondary polytope of (2,n) equals the state polytope ofI(K _n ) forn5 but not forn6. We also construct a non-regular triangulation of (2,n) forn9. We determine an explicit universal Gröbner basis ofI(K _n ) forn8. Potential applications in combinatorial optimization and random generation of graphs are indicated.Research partially supported by a doctoral fellowship of the National University of Mexico, the National Science Foundation, the David and Lucile Packard Foundation and the U.S. Army Research Office (through ACSyAM/MSI, Cornell).     

Bounds on the Chvátal Rank of Polytopes in the 0/1-Cube*

Gomorys and Chvátals cutting-plane procedure proves recursively the validity of linear inequalities for the integer hull of a given polyhedron. The Chvátal rank of the polyhedron is the number of rounds needed to obtain all valid inequalities. It is well known that the Chvátal rank can be arbitrarily large, even if the polyhedron is bounded, if it is 2-dimensional, and if its integer hull is a 0/1-polytope.We show that the Chvátal rank of polyhedra featured in common relaxations of many combinatorial optimization problems is rather small; in fact, we prove that the rank of every polytope contained in the n-dimensional 0/1-cube is at most n ² (1+log n). Moreover, we also demonstrate that the rank of any polytope in the 0/1-cube whose integer hull is defined by inequalities with constant coefficients is O(n).Finally, we provide a family of polytopes contained in the 0/1-cube whose Chvátal rank is at least (1 + ) n, for some > 0.* An extended abstract of this paper appeared in the Proceedings of the 7th International Conference on Integer Programming and Combinatorial Optimization [20].     

Projective lines over Jordan systems and geometry of Hermitian matrices

Any set of σ-Hermitian matrices of size n×n over a field with involution σ gives rise to a projective line in the sense of ring geometry and a projective space in the sense of matrix geometry. It is shown that the two concepts are based upon the same set of points, up to some notational differences.     

Imperfect and Nonideal Clutters: A Common Approach

We prove three theorems. First, Lovászs theorem about minimal imperfect clutters, including also Padbergs corollaries. Second, Lehmans result on minimal nonideal clutters. Third, a common generalization of these two. The endeavor of working out a common denominator for Lovászs and Lehmans theorems leads, besides the common generalization, to a better understanding and simple polyhedral proofs of both.* Visiting of the French Ministry of Research and Technology, laboratoire LEIBNIZ, Grenoble, November 1995—April 1996.     

Revlex-initial 0/1-polytopes

We introduce revlex-initial 0/1-polytopes as the convex hulls of reverse-lexicographically initial subsets of 0/1-vectors. These polytopes are special knapsack-polytopes. It turns out that they have remarkable extremal properties. In particular, we use these polytopes in order to prove that the minimum numbers g_nfac(d,n) of facets and the minimum average degree g_avdeg(d,n) of the graph of a d-dimensional 0/1-polytope with n vertices satisfy g_nfac(d,n)?3d and g_avdeg(d,n)?d+4. We furthermore show that, despite the sparsity of their graphs, revlex-initial 0/1-polytopes satisfy a conjecture due to Mihail and Vazirani, claiming that the graphs of 0/1-polytopes have edge-expansion at least one.     

The polytope of win vectors

Imagine a graph as representing a fixture list with vertices corresponding to teams, and the number of edges joiningu andv as representing the number of games in whichu andv have to play each other. Each game ends in a win, loss, or tie and we say a vector =(w ₁,...,w _n) is awin vector if it represents the possible outcomes of the games, withw _i denoting the total number of games won by teami. We study combinatorial and geometric properties of the set of win vectors and, in particular, we consider the problem of counting them. We construct a fully polynomial randomized approximation scheme for their number in dense graphs. To do this we prove that the convex hull of the set of win vectors ofG forms an integral polymatroid and then use volume approximation techniques. Supported by the “DAAD Doktorandenstipendium des zweiten Hochschulsonderprogrammes HSPII/AUFE”. Partially supported by RAND-REC EC US030.     

Alexandrov’s inequality and conjectures on some Toeplitz matrices

We study determinant inequalities for certain Toeplitz-like matrices over C. For fixed n and N ? 1, let Q be the n × (n + N − 1) zero-one Toeplitz matrix with Q_ij = 1 for 0 ? j − i ? N − 1 and Q_ij = 0 otherwise. We prove that det(QQ^∗) is the minimum of det(RR^∗) over all complex matrices R with the same dimensions as Q satisfying ∣R_ij∣ ? 1 whenever Q_ij = 1 and R_ij = 0 otherwise. Although R has a Toeplitz-like band structure, it is not required to be actually Toeplitz. Our proof involves Alexandrov’s inequality for polarized determinants and its generalizations. This problem is motivated by Littlewood’s conjecture on the minimum 1-norm of N-term exponential sums on the unit circle. We also discuss polarized Bazin-Reiss-Picquet identities, some connections with k-tree enumeration, and analogous conjectured inequalities for the elementary symmetric functions of QQ^∗.     

Boundedness of optimal matrices in extremal multigraph and digraph problems

We consider multigraphs in which any two vertices are joined by at mostq edges, and study the Turán-type problem for a given family of forbidden multigraphs. In the caseq=2, answering a question of Brown, Erds and Simonovits, we obtain an explicit upper bound on the size of the matrix generating an asymptotical solution of the problem. In the caseq>2 we show that some analogous statements do not hold, and so disprove a conjecture of Brown, Erds and Simonovits.     

On switching paths polyhedra

A class of integer polyhedra with totally dual integral (tdi) systems is proposed, which generalizes and unifies the “Switching Paths Polyhedra” of Hoffman (introduced in his generalization of Max Flow-Min Cut) and such polyhedra as the convex hull of (the incidence vectors of) all “path-closed sets” of an acyclic digraph, or the convex hull of all sets partitionable intok path-closed sets. As an application, new min-max theorems concerning the mentioned sets are given. A general lemma on when a tdi system of inequalities is box tdi is also given and used.     

Applications of a theorem by Ky Fan in the theory of graph energy

The energy of a graph G is equal to the sum of the absolute values of the eigenvalues of G, which in turn is equal to the sum of the singular values of the adjacency matrix of G. Let X, Y, and Z be matrices, such that X+Y=Z. The Ky Fan theorem establishes an inequality between the sum of the singular values of Z and the sum of the sum of the singular values of X and Y. This theorem is applied in the theory of graph energy, resulting in several new inequalities, as well as new proofs of some earlier known inequalities.