Incidence matrices and inequalities for combinatorial designs

In this paper we use incidence matrices of block designs and row–column designs to obtain combinatorial inequalities. We introduce the concept of nearly orthogonal Latin squares by modifying the usual definition of orthogonal Latin squares. This concept opens up interesting combinatorial problems and is expected to be useful in planning experiments by statisticians. © 2002 John Wiley & Sons, Inc. J Combin Designs 10: 17–26, 2002     

Enumerating bases of self-dual matroids

We define involutively self-dual matroids and prove that an enumerator for their bases is the square of a related enumerator for their self-dual bases. This leads to a new proof of Tutte's theorem that the number of spanning trees of a central reflex is a perfect square, and it solves a problem posed by Kalai about higher dimensional spanning trees in simplicial complexes. We also give a weighted version of the latter result.We give an algebraic analogue relating to the critical group of a graph, a finite abelian group whose order is the number of spanning trees of the graph. We prove that the critical group of a central reflex is a direct sum of two copies of an abelian group, and conclude with an analogous result in Kalai's setting.     

On some combinatorial properties of algebraic matroids

It was proved implicitly by Ingleton and Main and explicitly by Lindström that if three lines in the algebraic matroid consisting of all elements of an algebraically closed field are not coplanar, but any two of them are, then they pass through one point. This theorem is extended to a more general result about the intersection of subspaces in full algebraic matroids. This result is used to show that the minimax theorem for matroid matching, proved for linear matroids by Lovász, remains valid for algebraic matroids.     

Subgraphs as circuits and bases of matroids

As is well known, the cycles of any given graph G may be regarded as the circuits of a matroid defined on the edge set of G. The question of whether other families of connected graphs exist such that, given any graph G, the subgraphs of G isomorphic to some member of the family may be regarded as the circuits of a matroid defined on the edge set of G led us, in two other papers, to the proof of some results concerning properties of the cycles when regarded as circuits of such matroids. Here we prove that the wheels share many of these properties with the cycles. Moreover, properties of subgraphs which may be regarded as bases of such matroids are also investigated.     

Persistency in combinatorial optimization problems on matroids

Optimization problems on matroids are generalizations of such important combinatorial optimization problems like the problem of minimum spanning tree of a graph, the bipartite matching problem, flow problems, etc. We analyze algorithms for finding the maximum weight independent set of a matroid and for finding a maximum cardinality intersection of two matroids and extend them to obtain the so-called “persistency” partition of the basic set of the matroid, where contain elements belonging to all optimum solutions; contain elements not belonging to any optimum solution; contain elements that belong to some but not to all optimum solutions.     

An exchange theorem for bases of matroids

Theorem. Given two basesB₁andB₂of a matroid ($\text{M}$, r), and a partitionB₁ = X₁ ∪ Y₁, there is a partitionB₂ = X₂ ∪ Y₂such thatX₁ ∪ Y₂andX₂ ∪ Y₁are both bases of$\text{M}$.     

Complexity of packing common bases in matroids

Mathematical Programming - One of the most intriguing unsolved questions of matroid optimization is the characterization of the existence of k disjoint common bases of two matroids. The...     

Oriented matroids, complex manifolds, and a combinatorial model for BU

We introduce a new notion of complex oriented matroid and develop some basic properties of this object. Our definition of complex oriented matroids bears the same relationship to classical oriented matroids that the stratification of the complex plane into nine components corresponding to the signs of the complex and real parts has with the three-component sign stratification of the real line. We then use these complex oriented matroids to set up the foundations of a combinatorial version of complex geometry analogous to MacPherson's combinatorial differential manifolds; in this world, the representing object for the functor of (combinatorial) complex vector bundles is the nerve of a poset of complex oriented matroids. We conclude by showing that this space is homotopy equivalent to the complex Grassmannian, thus deducing that our combinatorial world is able to completely capture the notion of complex vector bundles.     

Type-II matrices and combinatorial structures

Type-II matrices are a class of matrices used by Jones in his work on spin models. In this paper we show that type-II matrices arise naturally in connection with some interesting combinatorial and geometric structures.     

On combinatorial optimization problems on matroids with uncertain weights

In this paper the combinatorial optimization problem on weighted matroid is considered. It is assumed that the weights in the problem are ill-known and they are modeled as fuzzy intervals. The optimality of solutions and the optimality of elements are characterized. This characterization is performed in the setting of possibility theory. A method of choosing a solution under uncertainty is also proposed.     

Triangular matrices and combinatorial inversion formulas

The paper is devoted to the construction of the matrix inverse of an infinite triangular matrix and to finding the connection coefficients between polynomial sequences and general combinatorial inversion formulas.     

Invariant factors of combinatorial matrices

The Smith normal forms of an Hadamard matrix of order 4m (m square-free), and of the incidence matrix of a (ν, k, λ) configuration (n=k−λ square-free (n, λ)=1), are determined.     

On Mills's conjecture on matroids with many common bases

In this paper, we shall prove a conjecture of Mills: for two (k+1)-connected matroids whose symmetric difference between their collections of bases has size at most k, there is a matroid that is obtained from one of these matroids by relaxing n₁ circuit-hyperplanes and from the other by relaxing n₂ circuit-hyperplanes, where n₁ and n₂ are non-negative integers such that n₁+n₂k     

Integral and rational completions of combinatorial matrices

Earlier results by Marshall Hall on integral completions of matrices satisfying orthogonality conditions are extended as far as possible, with special attention given to the Hadamard case. A result on restricting the denominators of rational completions to a power of 2 is also given.     

A combinatorial problem involving graphs and matrices

In this paper we discuss a combinatorial problem involving graphs and matrices. Our problem is a matrix analogue of the classical problem of finding a system of distinct representatives (transversal) of a family of sets and relates closely to an extremal problem involving 1-factors and a long standing conjecture in the dimension theory of partially ordered sets. For an integer n ?1, let n denote the n element set {1,2,3,…, n}. Then let A be a k×t matrix. We say that A satisfies property P(n, k) when the following condition is satisfied: For every k-taple (x₁,x₂,…,x_k?n^k there exist k distinct integers j₁,j₂,…,j_k so that x_i= a_ii for i= 1,2,…,k. The minimum value of t for which there exists a k × t matrix A satisfying property P(n,k) is denoted by f(n,k). For each k?1 and n sufficiently large, we give an explicit formula for f(n, k): for each n?1 and k sufficiently large, we use probabilistic methods to provide inequalities for f(n,k).     

Self-dual codes from orbit matrices and quotient matrices of combinatorial designs

In this paper we give constructions of self-orthogonal and self-dual codes, with respect to certain scalar products, with the help of orbit matrices of block designs and quotient matrices of symmetric (group) divisible designs (SGDDs) with the dual property. First we describe constructions from block designs and their extended orbit matrices, where the orbit matrices are induced by the action of an automorphism group of the design. Further, we give some further constructions of self-dual codes from symmetric block designs and their orbit matrices. Moreover, in a similar way as for symmetric designs, we give constructions of self-dual codes from SGDDs with the dual property and their quotient matrices.     

Perfect difference families,perfect difference matrices,and related combinatorial structures

The existence problems of perfect difference families with block size k, k=4,5, and additive sequences of permutations of length n, n=3,4, are two outstanding open problems in combinatorial design theory for more than 30 years. In this article, we mainly investigate perfect difference families with block size k=4 and additive sequences of permutations of length n=3. The necessary condition for the existence of a perfect difference family with block size 4 and order v, or briefly (v, 4,1)‐PDF, is v≡1(mod12), and that of an additive sequence of permutations of length 3 and order m, or briefly ASP (3, m), is m≡1(mod2). So far, (12t+1,4,1)‐PDFs with t<50 are known only for t=1,4−36,41,46 with two definiteexceptions of t=2,3, and ASP (3, m)'s with odd 3<m<200 are known only for m=5,7,13−29,35,45,49,65,75,85,91,95,105,115,119,121,125,133,135,145,147,161,169,175,189,195 with two definite exceptions of m=9,11. In this article, we show that a (12t+1,4,1)‐PDF exists for any t⩽1,000 except for t=2,3, and an ASP (3, m) exists for any odd 3<m<200 except for m=9,11 and possibly for m=59. The main idea of this article is to use perfect difference families and additive sequences of permutations with “holes”. We first introduce the concepts of an incomplete perfect difference matrix with a regular hole and a perfect difference packing with a regular difference leave, respectively. We show that an additive sequence of permutations is in fact equivalent to a perfect difference matrix, then describe an important recursive construction for perfect difference matrices via perfect difference packings with a regular difference leave. Plenty of perfect difference packings with a desirable difference leave are constructed directly. We also provide a general recursive construction for perfect difference packings, and as its applications, we obtain extensive recursive constructions for perfect difference families, some via incomplete perfect difference matrices with a regular hole. Examples of perfect difference packings directly constructed are used as ingredients in these recursive constructions to produce vast numbers of perfect difference families with block size 4. © 2010 Wiley Periodicals, Inc. J Combin Designs 18: 415–449, 2010     

Factored matrices can generate combinatorial identities

By identifying the terms in the LU decomposition of various matrices, one produces combinatorial identities. Examples are given with formulas involving binomial coefficients and other numbers arising from simple recurrence formulas, number-theoretic functions, q-series, and orthogonal polynomials.     

Some combinatorial properties of centrosymmetric matrices

The elements in the group of centrosymmetric n×n permutation matrices are the extreme points of a convex subset of n²-dimensional Euclidean space, which we characterize by a very simple set of linear inequalities, thereby providing an interesting solvable case of a difficult problem posed by L. Mirsky, as well as a new analogue of the famous theorem on doubly stochastic matrices due to G. Birkhoff. Several further theorems of a related nature also are included.