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 designs and formally self-dual codes

Binary formally self-dual (f.s.d.) even codes are the one type of divisible [2n, n] codes which need not be self-dual. We examine such codes in this paper. On occasion a f.s.d. even [2n, n] code can have a larger minimum distance than a [2n, n] self-dual code. We give many examples of interesting f.s.d even codes. We also obtain a strengthening of the Assmus-Mattson theore. IfC is a f.s.d. extremal code of lengthn2 (mol 8) [n 6 (mod 8)], then the words of a fixed weight inC C hold a 3-design [1-design]. Finally, we show that the extremal f.s.d. codes of lengths 10 and 18 are unique.The author thanks the University of Illinois at Chicago for their hospitality while this work was in progress.This work was supported in part by NSA Grant MDA 904-91-H-0003.     

A study on monotone self-dual Boolean functions

This paper shows that monotone self-dual Boolean functions in irredundant disjuntive normal form (IDNF) do not have more variables than disjuncts. Monotone self-dual Boolean functions in IDNF with the same number of variables and disjuncts are examined. An algorithm is proposed to test whether a monotone Boolean function in IDNF with n variables and n disjuncts is self-dual. The runtime of the algorithm is O(n³).     

Extremal self-dual codes from symmetric designs

A method is given for constructing extremal binary self-dual [42, 21, 8]-codes from certain symmetric 2-(41, 16, 6) designs.     

Boolean sublattices connected with minimization problems on matroids

It is noted that the decomposition of a network presented by J.C. Picard and M. Queyranne through an algorithmic argument may be defined from a general lattice-theoretic result for more general problems for which the equalities of maximum-flow minimum-cut type hold.     

On the fractional chromatic number of monotone self-dual Boolean functions

We compute the exact fractional chromatic number for several classes of monotone self-dual Boolean functions. We characterize monotone self-dual Boolean functions in terms of the optimal value of an LP relaxation of a suitable strengthening of the standard IP formulation for the chromatic number. We also show that determining the self-duality of a monotone Boolean function is equivalent to determining the feasibility of a certain point in a polytope defined implicitly.     

Boolean sums of sets of certain designs

In this note the author applies Boolean sum operation on sets of certain designs to get new series of designs.     

Terms that are self-dual in Boolean algebras but not in MO 2

An absorption law is an identity of the form p = x. The ternary function x+y+z (ring addition) in Boolean algebras satisfies three absorption laws in two variables. If a term satisfies these three identities in a variety, it is called a minority term for that variety. We construct a minority term p for orthomodular lattices such the identity defines Boolean algebras modulo orthomodular lattices. (The dual of p is denoted by .) Consequently, having a unique minority term function characterizes Boolean algebras among orthomodular lattices. Our main result generalizes this example to arbitrary arity and arbitrary consistent sets of 2-variable absorption laws. Presented by J. Berman.     

On the support designs of extremal binary doubly even self-dual codes

Let \(D\) be the support design of the minimum weight of an extremal binary doubly even self-dual \([24m,12m,4m+4]\) code. In this note, we consider the case when \(D\) becomes a \(t\) -design with \(t \ge 6\) .     

The existence of extremal self-dual [50,25,10] codes and quasi-symmetric 2-(49,9,6) designs

All extremal binary self-dual [50,25,10] codes with an automorphism of order 7 are enumerated. Up to equivalence, there are four such codes, three with full automorphism group of order 21, and one code with full group of order 7. The minimum weight codewords yield quasi-symmetric 2-(49,9,6) designs.Research supported in part by NSA grant MDA904-95-H-1019.     

Oriented matroids

In this paper, the basic properties of oriented matroids are examined. A topological representation theorem for oriented matroids is proven, utilizing the notion of an “arrangement of pseudo-hemispheres”. The duality theorem of linear programming is extended to oriented matroids.     

Irredundant self-dual bases for self-dual lattice varieties

For any finitely based self-dual variety of lattices, we determine the sizes of all equational bases that are both irredundant and self-dual. We make the same determination for {0, 1}-lattice varieties.Received July 11, 2002; accepted in final form August 27, 2004.     

Biased graphs whose matroids are special binary matroids

Abiased graph is a graph together with a class of polygons such that no theta subgraph contains exactly two members of the class. To a biased graph are naturally associated three edge matroids:G(), L(), L ₀ (). We determine all biased graphs for which any of these matroids is isomorphic to the Fano plane, the polygon matroid ofK ₄,K ₅ orK _3,3, any of their duals, Bixby's regular matroidR ₁₀, or the polygon matroid ofK _m form > 5. In each case the bias is derived from edge signs. We conclude by finding the biased graphs for whichL ₀ () is not a graphic [or, regular matroid but every proper contraction is.Research supported by National Science Foundation grant DMS-8407102 and SGPNR grant 85Z0701Visiting Research Fellow, 1984–1985     

Unipancyclic matroids

Analogous to the concept of uniquely pancyclic graphs, we define a uniquely pancyclic (UPC) matroid of rank $r$ to be a (simple) rank-$r$ matroid containing exactly one circuit of each length $?$ for $3\le ?\le r+1$. Our discussion addresses the existence of graphic, binary, and transversal representations of UPC matroids. Using Shi’s results, which catalogued exactly seven non-isomorphic UPC graphs, we produce a nongraphic binary UPC matroid of rank 24. We consider properties of binary UPC matroids in general, and prove that all binary UPC matroids have a connectivity of $2$.     

Cyclotomic and simplicial matroids

We show that two naturally occurring matroids representable over ℚ are equal: thecyclotomic matroid μ_n represented by then ^th roots of unity 1, ζ, ζ², …, ζ^n-1 inside the cyclotomic extension ℚ(ζ), and a direct sum of copies of a certain simplicial matroid, considered originally by Bolker in the context of transportation polytopes. A result of Adin leads to an upper bound for the number of ℚ-bases for ℚ(ζ) among then ^th roots of unity, which is tight if and only ifn has at most two odd prime factors. In addition, we study the Tutte polynomial of μ_n in the case thatn has two prime factors. First author supported by NSF Postdoctoral Fellowship. Second author supported by NSF grant DMS-0245379.     

On Tutte polynomial expansion formulas in perspectives of matroids and oriented matroids

We introduce the active partition of the ground set of an oriented matroid perspective (or morphism, or quotient, or strong map) on a linearly ordered ground set. The reorientations obtained by arbitrarily reorienting parts of the active partition share the same active partition. This yields an equivalence relation for the set of reorientations of an oriented matroid perspective, whose classes are enumerated by coefficients of the Tutte polynomial, and a remarkable partition of the set of reorientations into Boolean lattices, from which we get a short direct proof of a 4-variable expansion formula for the Tutte polynomial in terms of orientation activities. This formula was given in the last unpublished preprint by Michel Las Vergnas; the above equivalence relation and notion of active partition generalize a former construction in oriented matroids by Michel Las Vergnas and the author; and the possibility of such a proof technique in perspectives was announced in the aforementioned preprint. We also briefly highlight how the 5-variable expansion of the Tutte polynomial in terms of subset activities in matroid perspectives comes in a similar way from the known partition of the power set of the ground set into Boolean lattices related to subset activities (and we complete the proof with a property which was missing in the literature). In particular, the paper applies to matroids and oriented matroids on a linearly ordered ground set, and applies to graph and directed graph homomorphisms on a linearly ordered edge-set.     

Gammoids and transversal matroids

The two main results of this paper identify the “strict gammoids” of Mason [7] with duals of transvesal matroids, and gammoids in general with contractions of transversal matroids. Both theorems derive from a fundamental construction which we also use, inter alia, to establish a duality between the graph theorems of Menger and König.     

Every self-dual ordering has a self-dual linear extension

In this note, it is showed that every self-dual ordering has a self-dual linear extension.