Coxeter matroid polytopes

If Δ is a polytope in real affine space, each edge of Δ determines a reflection in the perpendicular bisector of the edge. The exchange groupW (Δ) is the group generated by these reflections, and Δ is a (Coxeter) matroid polytope if this group is finite. This simple concept of matroid polytope turns out to be an equivalent way to define Coxeter matroids. The Gelfand-Serganova Theorem and the structure of the exchange group both give us information about the matroid polytope. We then specialize this information to the case of ordinary matroids; the matroid polytope by our definition in this case turns out to be a facet of the classical matroid polytope familiar to matroid theorists. This work was supported in part by NSA grant MDA904-95-1-1056.     

Recognizing graphic matroids

There is no polynomially bounded algorithm to test if a matroid (presented by an “independence oracle”) is binary. However, there is one to test graphicness. Finding this extends work of previous authors, who have given algorithms to test binary matroids for graphicness. Our main tool is a new result that ifM′ is the polygon matroid of a graphG, andM is a different matroid onE(G) with the same rank, then there is a vertex ofG whose star is not a cocircuit ofM.     

On minors of non-binary matroids

No binary matroid has a minor isomorphic toU ₄ ² , the “four-point line”, and Tutte showed that, conversely, every non-binary matroid has aU ₄ ² minor. However, more can be said about the element sets ofU ₄ ² minors and their distribution. Bixby characterized those elements which are inU ₄ ² minors; a matroidM has aU ₄ ² minor using elementx if and only if the connected component ofM containingx is non-binary. We give a similar (but more complicated) characterization for pairs of elements. In particular, we prove that for every two elements of a 3-connected non-binary matroid, there is aU ₄ ² minor using them both.     

Connected hyperplanes in binary matroids

For a 3-connected binary matroid M, let dim_A(M) be the dimension of the subspace of the cocycle space spanned by the non-separating cocircuits of M avoiding A, where A⊆E(M). When A=∅, Bixby and Cunningham, in 1979, showed that dim_A(M)=r(M). In 2004, when |A|=1, Lemos proved that dim_A(M)=r(M)-1. In this paper, we characterize the 3-connected binary matroids having a pair of elements that meets every non-separating cocircuit. Using this result, we show that 2dim_A(M)?r(M)-3, when M is regular and |A|=2. For |A|=3, we exhibit a family of cographic matroids with a 3-element set intersecting every non-separating cocircuit. We also construct the matroids that attains McNulty and Wu’s bound for the number of non-separating cocircuits of a simple and cosimple connected binary matroid.     

Embeddings ofC(Δ) andL 1[0, 1] in Banach lattices

It is proved that ifE is a separable Banach lattice withE′ weakly sequentially complete,F is a Banach space andT:E→F is a bounded linear operator withT′F′ non-separable, then there is a subspaceG ofE, isomorphic toC(Δ), such thatT _G is an isomorphism, whereC(Δ) denotes the space of continuous real valued functions on the Cantor discontinuum. This generalizes an earlier result of the second-named author. A number of conditions are proved equivalent for a Banach latticeE to contain a subspace order isomorphic toC(Δ). Among them are the following:L ¹ is lattice isomorphic to a sublattice ofE′;C(Δ)′ is lattice isomorphic to a sublattice ofE′; E contains an order bounded sequence with no weak Cauchy subsequence;E has a separable closed sublatticeF such thatF′ does not have a weak order unit. The research of both authors was partially supported by the National Science Foundation, NSF Grant No MPS 71-02839 A04.     

The complexity of computing the tutte polynomial on transversal matroids

The complexity of computing the Tutte polynomialT(M,x,y) is determined for transversal matroidM and algebraic numbersx andy. It is shown that for fixedx andy the problem of computingT(M,x,y) forM a transversal matroid is #P-complete unless the numbersx andy satisfy (x−1)(y−1)=1, in which case it is polynomial-time computable. In particular, the problem of counting bases in a transversal matroid, and of counting various types of “matchable” sets of nodes in a bipartite graph, is #P-complete.     

The graph induced by affine <Emphasis Type="Italic">M</Emphasis>-flats over finite fields II

Let AG(n, F _q) be the n-dimensional affine space over F _q, where F _q is a finite field with q elements. Denote by Γ ^(m) the graph induced by m-flats of AG(n, F _q). For any two adjacent vertices E and F of is studied. In particular, sizes of maximal cliques in Γ ^(m) are determined and it is shown that Γ ^(m) is not edge-regular when m<n−1. Supported by the National Natural Science Foundation of China (19571024) and Hunan Provincial Department of Education (02C512).     

Matching behaviour is asymptotically normal

Ak-matching in a graphG is a set ofk edges, no two of which have a vertex in common. The number of these inG is writtenp(G, k). Using an idea due to L. H. Harper, we establish a condition under which these numbers are approximately normally distributed. We show that our condition is satisfied ifn=|V(G)| is large compared to the maximum degree Δ of a vertex inG(i.e. Δ=o(n)) orG is a large complete graph. One corollary of these results is that the number of points fixed by a randomly chosen involution in the symmetric groupS is asymptotically normally distributed.     

Forests and score vectors

Thescore vector of a labeled digraph is the vector of out-degrees of its vertices. LetG be a finite labeled undirected graph without loops, and let σ(G) be the set of distinct score vectors arising from all possible orientations ofG. Let ϕ(G) be the set of subgraphs ofG which are forests of labeled trees. We display a bijection between σ(G) and ϕ(G). Supported in part by ONR Contract N00014-76-C-0366.     

A problem of P. Seymour on nonbinary matroids

The following statement fork=1, 2, 3 has been proved by Tutte [4], Bixby [1] and Seymour [3] respectively: IfM is ak-connected non-binary matroid andX a set ofk-1 elements ofM, thenX is contained in someU ₄ ² minor ofM. Seymour [3] asks whether this statement remains true fork=4; the purpose of this note is to show that it does not and to suggest some possible alternatives. Supported in part by the National Science Foundation     

The quotient field as a torsion-free covering module

R will denote a commutative integral domain with quotient fieldQ. A torsion-free cover of a moduleM is a torsion-free moduleF and anR-epimorphism σ:F→M such that given any torsion-free moduleG and λ∈Hom _R (G, M) there exists μ∈Hom _R (G,F) such that σμ=λ. It is known that ifM is a maximal ideal ofR, R→R/M is a torsion-free cover if and only ifR is a maximal valuation ring. LetE denote the injective hull ofR/M thenR→R/M extends to a homomorphismQ→E. We give necessary and sufficient conditions forQ→E to be a torsion-free cover.     

Coordinatizing R-trees in terms of universal c-trees

A complete ℝ-treeT will be constructed such that, for everyxσT, the cardinality of the set of connected components ofT{x} is the same and equals a pre-given cardinalityc; by this construction simultaneously the valuated matroid of the ends of this ℝ-tree is given. In addition, for any arbitrary ℝ-tree, an embedding into such a “universalc-tree” (for suitablec) will be constructed.     

On a class of difference sequences related to the ℓ<Superscript>p</Superscript> space defined by Orlicz functions

In this article we introduce the difference sequence space m(M, Δ, φ) using the Orlicz function. We study its different properties like solidity, completeness etc. Also we obtain some inclusion relations involving the space m(M, Δ, φ).      

On a problem of Erdős concerning property B

A family ℱ of sets has propertyB if there exists a setS such thatS∩F≠0 andS⊄F for everyF∈ℱ. ℱ has propertyB(s) if there exists a setS such that 0<|F∩S|<s for everyF∈ℱ. Denote bym(n) (respectivelym(n, s)) the size of a smallest family ofn-element sets not having propertyB (respectivelyB(s)). P. Erdős has asked whetherm(n, s)≧m (s) for alln≧s. We show that, in general, this inequality does not hold.     

Maximality of analytic operator algebras

LetM be a σ-finite von Neumann algebra andα be an action ofR onM. LetH ^∞(α) be the associated analytic subalgebra; i.e.H ^∞(α)={X ∈M: sp_∞(X) [0, ∞]}. We prove that every σ-weakly closed subalgebra ofM that containsH ^∞(α) isH ^∞(γ) for some actionγ ofR onM. Also we show that (assumingZ(M)∩M ^α = Ci)H ^∞(α) is a maximal σ-weakly closed subalgebra ofM if and only if eitherH ^∞(α)={A ∈M: (I−F)xF=0} for some projectionF ∈M, or sp(α)=Γ(α).     

A matroid generalization of a result of Dirac

This paper generalizes a theorem of Dirac for graphs by proving that ifM is a 3-connected matroid, then, for all pairs {a,b} of distinct elements ofM and all cocircuitsC ^* ofM, there is a circuit that contains {a,b} and meetsC ^*. It is also shown that, although the converse of this result fails, the specified condition can be used to characterize 3-connected matroids.The author's research was partially supported by a grant from the National Security Agency.     

Decomposition of binary matroids

We prove results relating to the decomposition of a binary matroid, including its uniqueness when the matroid is cosimple. We extend the idea of “freedom” of an element in a matroid to “freedom” of a set, and show that there is a unique maximal integer polymatroid inducing a given binary matroid.     

Intersections ofk-element sets

LetF be a collection ofk-element sets with the property that the intersection of no two should be included in a third. We show that such a collection of maximum size satisfies .2715k+o(k)≦≦log₂ |F|≦.7549k+o(k) settling a question raised by Erdős. The lower bound is probabilistic, the upper bound is deduced via an entropy argument. Some open questions are posed. This research has been supported in part by the Office of Naval Research under Contract N00014-76-C-0366. Supported in part by a NSF postdoctoral Fellowship.     

Analytic discs, plurisubharmonic hulls, and non-compactness of the -Neumann operator

We show that a complex manifold M in the boundary of a smooth bounded pseudoconvex domain Ω in is an obstruction to compactness of the -Neumann operator on Ω, provided that at some point of M, the Levi form of bΩ has the maximal possible rank n−1−dim(M) (i.e. the boundary is strictly pseudoconvex in the directions transverse to M). In particular, an analytic disc is an obstruction, provided that at some point of the disc, the Levi form has only one zero eigenvalue (i.e. the eigenvalue zero has multiplicity one). We also show that a boundary point where the Levi form has only one zero eigenvalue can be picked up by the plurisubharmonic hull of a set only via an analytic disc in the boundary. Research supported in part by NSF grant number DMS-0100517.