Search

For a permutation p, and the corresponding permutation matrix, we introduce the notion of discrete derivative, obtained by taking differences of successive entries in p. We characterize the possible derivatives of permutations, and consider questions for permutations with certain properties satisfied by the derivative. For instance, we consider permutations with distinct derivatives, and the relationship to so-called Costas arrays.

We investigate convex polytopes of doubly stochastic matrices having special structures: symmetric, Hankel-symmetric, centrosymmetric, and both symmetric and Hankel-symmetric. We determine dimensions of these polytopes and classify their extreme points. We also determine a basis of the real vector spaces generated by permutation matrices with these special structures.

Let n≥2 be an integer. The complete graph Knwith a 1‐factor Fremoved has a decomposition into Hamilton cycles if and only if nis even. We show that Kn−Fhas a decomposition into Hamilton cycles which are symmetric with respect to the 1‐factor Fif and only if n≡2, 4 mod 8. We also show that the complete bipartite graph Kn, nhas a symmetric Hamilton cycle decomposition if and only if nis even, and that if Fis a 1‐factor of Kn, n, then Kn, n−Fhas a symmetric Hamilton cycle decomposition if and only if nis odd. © 2010 Wiley Periodicals, Inc. J Combin Designs 19:1‐15, 2010

Ao and Hanson, and Guiduli, Gyárfás, Thomassé and Weidl independently, proved the following result: For any tournament score sequence S = (s1, s2, … ,sn) with s1≤s2 ≤ … ≤ sn, there exists a tournament T on vertex set {1,2, …, n} such that the score of each vertex i is si and the sub-tournaments of T on both the even and the odd indexed vertices are transitive in the given order; that is, i dominates j whenever i > j and i ≡ j (mod 2). In this note, we give a much shorter proof of the result. In the course of doing so, we show that the score sequence of a tournament satisfies a set of inequalities which are individually stronger than the well-known set of inequalities of Landau, but collectively the two sets of inequalities are equivalent. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 244–254, 2001

Ao and Hanson, and Guiduli, Gyárfás, Thomassé and Weidl independently, proved the following result: For any tournament score sequence S= (s1, s2, … ,sn) with s1≤s2≤ … ≤ sn, there exists a tournament Ton vertex set {1,2, …, n} such that the score of each vertex iis siand the sub‐tournaments of Ton both the even and the odd indexed vertices are transitive in the given order; that is, idominates jwhenever i> jand i≡ j(mod 2). In this note, we give a much shorter proof of the result. In the course of doing so, we show that the score sequence of a tournament satisfies a set of inequalities which are individually stronger than the well‐known set of inequalities of Landau, but collectively the two sets of inequalities are equivalent. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 244–254, 2001

Abstract: The nested-subset hypothesis of Patterson and Atmar states that species composition on islands with less species richness is a proper subset of those on islands with greater species richness. The sum of species absences, referred to as gaps, was suggested as a metric for nestedness, and null models have been used to test whether or not island species exhibited nestedness. Simberloff and Martin stated that finding examples of non-nested faunas was difficult. We revisit previous analyses of nested faunas and introduce a new metric we call “discrepancy” which we recommend as a measure for nestedness. We also recommend that the sample spaces conserve both row sums (number of species per site) and column sums (number of sites per species) derived from the incidence matrix. We compare our results to previous analyses.

We investigate a method of combining two codes which we call the outer product. First-order Reed-Muller codes are outer products of a number of copies of the full binary space of length 2, and we apply our results to obtain cosets of the Reed-Muller codes which have no ancestors, that is, which are orphans.

Let $ \mathfrak{A}(R,S)$ $ m \times n$R and column sum vector S. A set $ I \times J(I \subseteq \{ 1, \ldots ,m\} ,J \subseteq \{ 1, \ldots ,n\} )$ $ \mathfrak{A}(R,S)$ $ I \times J$ $ I \times J$ $ I = \emptyset ,I = \{ 1, \ldots ,m\} ,J = \emptyset $ .

We define a class of functions called assignment functions, one of which is the permanent function. These functions evaluated at matrices of 0's and 1's are shown to be of applied and combinational interest. We define assignment polytopes which generalize the classical assignment polytope and use them to obtain bounds for the assignment function. We propose the determination of the minimum and maximum value of an assignment function on its corresponding assignment polytope and conjecture that the maximum value is 1. A natural conjecture for the minimum value is shown to be false. The minimum and maximum value are determined for special assignment functions.

Given an $ m \times m$ and a positive vector $ R = ({r_1}, \cdots ,{r_m})$ with positive main diagonal such that DAD has row sum vector .

We show how several classical results concerning inclusion regions and estimates for the eigenvalues of matrices can be unified and generalized by the use of directed graphs. Applications to nonnegative matricesM-matrices, and the spectra of graphs are given.

We prove the existence of two edge-disjoint multicolored spanning trees in any edge-coloring of a complete graph by perfect matchings; we conjecture that a full partition into multicolored spanning trees is always possible.

If $ A$ (its fully indecomposable exponent) that is fully indecomposable, and a smallest power of (its strict fully indecomposable exponent) starting from which all powers are fully indecomposable. We obtain bounds on these two exponents.

Dedicated to Leon Mirsky on the occasion of his sixtieth birthday.

Hankel and Toeplitz Matrices and Forms, by I. S. Iohvidov, "Nauka", Moscow, 1974. 263 pp. (in Russian).Probabilistic Methods in Combinatorics, by Paul Erdös and Joel Spencer.

Let G be a matching-covered, connected bipartite graph. We determine the dimension of the binary vector space which is spanned by the characteristic vectors of perfect matchings of G. We then show that the cutsets of G are those sets F of edges such that ∣Fx∩M∣ has the same parity for every perfect matching M of G.

We give new, primarily combinatorial proofs of the MacWilliams identifies which relate the weight distribution of a code to that of a dual.

We discuss primarily two applications of doubly stochastic matrices and related matrices. The first concerns a topic in communication theory called satellite-switched, time-division multiple-access systems, and we attempt to illuminate some results which have occured in the engineering literature. The second concerns a recent notion of a doubly stochastic automorphism of a graph. We prove several new theorems about doubly stochastic automorphisms of certain classes of graphs, and in particular, obtain a theorem of which Birkhoff's theorem for doubly stochastic matrices is a special case.

We characterize linear transformations on the vector space of $n \times n$ matrices of the form $A \to PAQ$ which preserve the combinatorial properties of irreducibility, reducibility, near reducibility, full indecomposability, decomposability, and near decomposability for nonnegative matrices. The minimality of such pairs $P,Q$ is also considered.

For an $n \times n$ complementary acyclic matrix Aof 0’s and l’s we show that the spectral radius $\rho ( A )$ of Asatisfies $\rho ( A )\geqq n - 2$ and determine those matrices Afor which equality holds. When Ais an $n \times n$ irreducible, complementary tree matrix, we also obtain that $\rho ( A )\leqq \rho _n $, where $\rho _n $ is the largest root of the polynomial $\lambda^3 - (n - 2 )\lambda^2 - ( n - 3 )\lambda - 1$.

We study both existence and structural properties of 2-multigraphs in the class [image omitted]  of all 2-multigraphs with a prescribed degree sequence D. A 2-multigraph in [image omitted]  defined to be parsimonious provided no 2-multigraph with the same degree sequence has fewer edges in its supporting (i.e., underlying) graph. In a parsimonious 2-multigraph G each connected component of the graph Gr formed by the edges of multiplicity 1 is either a star or a triangle. We attempt to understand the relationship between degree sequences and these graphs Gr.

We consider the problem of determining the minimum and maximum of the sum of the elements of the square of a matrix for the following classes of matrices:the (0, l)-matrices of order n with a specified number of l's; the symmetric (0,1)-matrices of order n with zero trace and with a specified number of l's above the main diagonal (adjacency matrices of graphs with a specified number of edges); and the subset of the latter consisting of adjacency matrices of connected graphs.

We investigate join-semilattices in which each element is assigned a nonnegative weight in a strictly increasing way. A join-subsemilattice of a Boolean lattice is weighted by cardinality, and we give a characterization of these in terms of the notion of a spread. The collection of flats with no coloops (isthmuses) of a matroid or pregeometry, partially ordered by set-theoretic inclusion, forms a join-semilattice which is weighted by rank. For transversal matroids these join-semilattices are isomorphic to join-subsemilattices of Boolean lattices. Using a previously obtained characterization of transversal matroids and results on weighted join-semilattices, we obtain another characterization of transversal matroids. The problem of constructing a transversal matroid whose join-semilattice of flats is isomorphic to a given join-subsemilattice of a Boolean lattice is then investigated.

We consider a face [image omitted]  of dimension (n2 - n)/2 of the polytope of n × n doubly stochastic matrices. We determine the minimum permanent on this face and show that the matrices in [image omitted]  which achieve this minimum permanent form a convex polytope whose dimension is asymptotic to the dimension of [image omitted]  Several problems and conjectures are proposed.

Let Gbe a graph whose vertices have positive degrees d1, …, dn, respectively, and let L(G) be the Laplacian matrix of G. When Gis a tree or a bipartite graph we obtain bounds for the permanent of L(G) both in terms of nonly and in terms of d1, …, dn. Improved bounds are obtained in terms of the diameter of Tand the size of a matching in T.

In a recent article [3] L. Mirsky proved a theorem which gives necessary and sufficient conditions for the existence of a finite integral matrix whose elements, row sums, and column sums all lie within prescribed bounds. Mirsky suggested to me the problem of extending his theorem to infinite matrices, and it is the solution of this problem that is presented in this note. To allow for extra generality, instead of prescribing upper and lower bounds for the row and column sums we shall prescribe upper and lower bounds for the row and column deficiencies (a term to be explained later). The theorem when upper and lower bounds for the row and column sums are prescribed is then a special case of the deficiency theorem. The solution of the problem depends on a construction of Mirsky [3] and a theorem of mine [1] concerning the existence of a partial transversal of a family of sets satisfying certain properties. As will be seen, we shall take a rather broad view of the notion of a matrix.