The structure of the 4-separations in 4-connected matroids

For a 2-connected matroid M, Cunningham and Edmonds gave a tree decomposition that displays all of its 2-separations. When M is 3-connected, two 3-separations are equivalent if one can be obtained from the other by passing through a sequence of 3-separations each of which is obtained from its predecessor by moving a single element from one side of the 3-separation to the other. Oxley, Semple, and Whittle gave a tree decomposition that displays, up to this equivalence, all non-trivial 3-separations of M. Now let M be 4-connected. In this paper, we define two 4-separations of M to be 2-equivalent if one can be obtained from the other by passing through a sequence of 4-separations each obtained from its predecessor by moving at most two elements from one side of the 4-separation to the other. The main result of the paper proves that M has a tree decomposition that displays, up to 2-equivalence, all non-trivial 4-separations of M.     

Constructing a 3-tree for a 3-connected matroid

In an earlier paper with Whittle, we showed that there is a tree that displays, up to a natural equivalence, all non-trivial 3-separations of a 3-connected matroid M. The purpose of this paper is to give a polynomial-time algorithm for constructing such a tree for M.     

On 3-connected minors of 3-connected matroids and graphs

Whittle proved, for k=1,2, that if N is a 3-connected minor of a 3-connected matroid M, satisfying r(M)−r(N)≥k, then there is a k-independent set I of M such that, for every x∈I, si(M/x) is a 3-connected matroid with an N-minor. In this paper, we establish this result for k=3. It is already known that it cannot be extended to greater values of k. But, here we also show that, in the graphic case, with the extra assumption that r(M)−r(N)≥6, we can guarantee the existence of a 4-independent set of M with such a property. Moreover, in the binary case, we show that if r(M)−r(N)≥5, then M has such a 4-independent set or M has a triangle T meeting 3 triads and such that M/T is a 3-connected matroid with an N-minor.     

Removing circuits in 3-connected binary matroids

For a k-connected graph or matroid M, where k is a fixed positive integer, we say that a subset X of E(M) is k-removable provided M?X is k-connected. In this paper, we obtain a sharp condition on the size of a 3-connected binary matroid to have a 3-removable circuit.     

On matroid separations of graphs

Let K be a connected and undirected graph, and M be the polygon matroid of K. Assume that, for some k ? 1, the matroid M is k-separable and k-connected according to the matroid separability and connectivity definitions of W. T. Tutte. In this paper we classify the matroid k-separations of M in terms of subgraphs of K.     

On the minor-minimal 3-connected matroids having a fixed minor

Let N be a minor of a 3-connected matroid M such that no proper 3-connected minor of M has N as a minor. This paper proves a bound on |E(M)−E(N)| that is sharp when N is connected.     

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.     

On the evaluation of the Eigenvalues of a banded toeplitz block matrix

Let A = (a_ij) be an n × n Toeplitz matrix with bandwidth k + 1, K = r + s, that is, a_ij = a_j−i, i, J = 1,… ,n, a_i = 0 if i > s and if i < -r. We compute p(λ)= det(A - λI), as well as p(λ)/p′(λ), where p′(λ) is the first derivative of p(λ), by using O(k log k log n) arithmetic operations. Moreover, if a_i are m × m matrices, so that A is a banded Toeplitz block matrix, then we compute p(λ), as well as p(λ)/p′(λ), by using O(m³k(log² k + log n) + m²k log k log n) arithmetic operations. The algorithms can be extended to the computation of det(A − λB) and of its first derivative, where both A and B are banded Toeplitz matrices. The algorithms may be used as a basis for iterative solution of the eigenvalue problem for the matrix A and of the generalized eigenvalue problem for A and B.     

Multi-Dimensional Pattern Matching with Dimensional Wildcards: Data Structures and Optimal On-Line Search Algorithms

We introduce a new multidimensional pattern matching problem that is a natural generalization of string matching, a well studied problem[1]. The motivation for its algorithmic study is mainly theoretical. LetA[1:n₁,…,1:n_d] be a text matrix withN = n₁…n_dentries andB[1:m₁,…,1:m_r] be a pattern matrix withM = m₁…m_rentries, whered ≥ r ≥ 1 (the matrix entries are taken from an ordered alphabet Σ). We study the problem of checking whether somer-dimensional submatrix ofAis equal toB(i.e., adecisionquery).Acan be preprocessed andBis given on-line. We define a new data structure for preprocessingAand propose CRCW-PRAM algorithms that build it inO(log N) time withN²/n_maxprocessors, wheren_max = max(n₁,…,n_d), such that the decision query forBtakesO(M) work andO(log M) time. By using known techniques, we would get the same preprocessing bounds but anO((^d_r)M) work bound for the decision query. The latter bound is undesirable since it can depend exponentially ond; our bound, in contrast, is independent ofdand optimal. We can also answer, in optimal work, two further types of queries: (a) anenumerationquery retrieving all ther-dimensional submatrices ofAthat are equal toBand (b) anoccurrencequery retrieving only the distinct positions inAthat correspond to all of these submatrices. As a byproduct, we also derive the first efficient sequential algorithms for the new problem.     

Bijective linear maps on semimodules spanned by Boolean matrices of fixed rank

Let M_m,n(B) be the semimodule of all m×n Boolean matrices where B is the Boolean algebra with two elements. Let k be a positive integer such that 2?k?min(m,n). Let B(m,n,k) denote the subsemimodule of M_m,n(B) spanned by the set of all rank k matrices. We show that if T is a bijective linear mapping on B(m,n,k), then there exist permutation matrices P and Q such that T(A)=PAQ for all A∈B(m,n,k) or m=n and T(A)=PA^tQ for all A∈B(m,n,k). This result follows from a more general theorem we prove concerning the structure of linear mappings on B(m,n,k) that preserve both the weight of each matrix and rank one matrices of weight k². Here the weight of a Boolean matrix is the number of its nonzero entries.     

Idempotence preserving maps between matrix spaces

Suppose 𝔽 is an arbitrary field of characteristic not 2 and 𝔽?≠?𝔽₃. Let M _n (𝔽) be the space of all n?×?n full matrices over 𝔽 and P _n (𝔽) the subset of M _n (𝔽) consisting of all n?×?n idempotent matrices and GL _n (𝔽) the subset of M _n (𝔽) consisting of all n?×?n invertible matrices. Let Φ_𝔽(n,?m) denote the set of all maps from M _n (𝔽) to M _m (𝔽) satisfying A???λB?∈?P _n (𝔽)???φ(A)???λφ(B)?∈?P _m (𝔽) for every A,?B?∈?M _n (𝔽) and λ?∈?𝔽, where m and n are integers with 3?≤?n?≤?m. It is shown that if φ?∈?Φ_𝔽(n,?m), then there exists T?∈?GL _m (𝔽) such that φ(A)?=?T?[A???I _p ?⊕?A ^t ???I _q ?⊕?0]T?^?1 for every A?∈?M _n (𝔽), where I ₀?=?0. This improves the results of some related references.     

On Maximum-sized k-Regular Matroids

 Let k be an integer exceeding one. The class of k-regular matroids is a generalization of the classes of regular and near-regular matroids. A simple rank-r regular matroid has the maximum number of points if and only if it is isomorphic to M(K _r+1), the cycle matroid of the complete graph on r+1 vertices. A simple rank-r near-regular matroid has the maximum number of points if and only if it is isomorphic to the simplification of , that is, the simplification of the matroid obtained, geometrically, by freely adding a point to a 3-point line of M(K _r+2) and then contracting this point. This paper determines the maximum number of points that a simple rank-r k-regular matroid can have and determines all such matroids having this number. With one exception, there is exactly one such matroid. This matroid is isomorphic to the simplification of , that is, the simplification of the matroid obtained, geometrically, by freely adding k independent points to a flat of M(K _r+k+1) isomorphic to M(K _k+2) and then contracting each of these points. Revised: July 27, 1998     

Spanning 3-ended trees in k-connected K 1,4-free graphs

A tree with at most m leaves is called an m-ended tree.Kyaw proved that every connected K1,4-free graph withσ4(G)n-1 contains a spanning 3-ended tree.In this paper we obtain a result for k-connected K1,4-free graphs with k 2.Let G be a k-connected K1,4-free graph of order n with k 2.Ifσk+3(G)n+2k-2,then G contains a spanning 3-ended tree.     

A Splitter Theorem Relative to a Fixed Basis

A standard matrix representation of a matroid M represents M relative to a fixed basis B, where contracting elements of B and deleting elements of E(M)–B correspond to removing rows and columns of the matrix, while retaining standard form. If M is 3-connected and N is a 3-connected minor of M, it is often desirable to perform such a removal while maintaining both 3-connectivity and the presence of an N-minor. We prove that, subject to a mild essential restriction, when M has no 4-element fans with a specific labelling relative to B, there are at least two distinct elements, s ₁ and s ₂, such that for each i ∈ {1, 2}, si(M/s _i ) is 3-connected and has an N-minor when s _i ∈ B, and co(M\s _i ) is 3-connected and has an N-minor when s _i ∈ E(M)–B. We also show that if M has precisely two such elements and P is the set of elements that, when removed in the appropriate way, retain the N-minor, then (P, E(M)–P) is a sequential 3-separation.     

Elements belonging to triangles in 3-connected matroids

An element e of a 3-connected matroid M is said to be superfluous provided M/e is 3-connected. In this paper, we show that a 3-connected matroid M with exactly k superfluous elements has at least

     

Cycles intersecting a prescribed vertex set

A graph is said to have property P(k,l)(k ? l) if for any X ∈ (^G_k) there exists a cycle such that |X ∩ V(C)| = l. Obviously an n-connected graph (n ? 2) satisfies P(n,n). In this paper, we study parameters k and l such that every n-connected graph satisfies P(k,l). We show that for r = 1 or 2 every n-connected graph satisfies P(n + r,n). For r = 3, there are infinitely many 3-connected graphs that do not satisfy P(6,3). However, if n ? max{3,(2r ?1)(r + 1)}, then every n-connected graph satisfies P(n + r,n).     

Trace cocharacters and the Kronecker products of Schur functions

It follows from the theory of trace identities developed by Procesi and Razmyslov that the trace cocharacters arising from the trace identities of the algebra M_r(F) of r×r matrices over a field F of characteristic zero are given by TC_r,n=∑_λΛr(n)χ^λχ^λ where χ^λχ^λ denotes the Kronecker product of the irreducible characters of the symmetric group associated with the partition λ with itself and Λ_r(n) denotes the set of partitions of n with r or fewer parts, i.e. the set of partitions λ=(λ₁λ_k) with kr. We study the behavior of the sequence of trace cocharacters TC_r,n. In particular, we study the behavior of the coefficient of χ^(ν,n−m) in TC_r,n as a function of n where ν=(ν₁ν_k) is some fixed partition of m and n−mν_k. Our main result shows that such coefficients always grow as a polynomial in n of degree r−1.     

Possible numbers of positive entries of imprimitive nonnegative matrices

Zhan, X., Extremal numbers of positive entries of imprimitive nonnegative matrix, Linear Algebra Appl. (in press) has determined the maximum and minimum numbers of positive entries of imprimitive irreducible nonnegative matrices with a given imprimitivity index. Let σ( A ) denote the number of positive entries of a matrix A. Let M(n,?k) and m(n,?k) denote the maximum and minimum numbers of positive entries of imprimitive irreducible nonnegative matrices of order n with a given imprimitivity index k, respectively. In this article, we prove that for any positive integer d with m(n,k)≤ d?≤?M(n,k), there exists an n?×?n irreducible nonnegative matrix A with imprimitivity index k such that?σ?(A)=d.     

Possible inertias for the hermitian part of A + BX

Given AεM_n (C) and BεM _n,k (C) all possible inertias occurring in the Hermitian part of A+BX are determined as X runs over M_k,n(C).     

A bound on the scrambling index of a primitive matrix using Boolean rank

The scrambling index of an n×n primitive matrix A is the smallest positive integer k such that A^k(A^t)^k=J, where A^t denotes the transpose of A and J denotes the n×n all ones matrix. For an m×n Boolean matrix M, its Boolean rank b(M) is the smallest positive integer b such that M=AB for some m×b Boolean matrix A and b×n Boolean matrix B. In this paper, we give an upper bound on the scrambling index of an n×n primitive matrix M in terms of its Boolean rank b(M). Furthermore we characterize all primitive matrices that achieve the upper bound.