Linear algebra methods for forbidden configurations

We say a matrix is simple if it is a (0,1)-matrix with no repeated columns. Given m and a k×l (0,1)-matrix F we define forb(m,F) as the maximum number of columns in a simple m-rowed matrix A for which no k×l submatrix of A is a row and column permutation of F. In set theory notation, F is a forbidden trace. For all k-rowed F (simple or non-simple) Füredi has shown that forb(m,F) is O(m ^k ). We are able to determine for which k-rowed F we have that forb(m,F) is O(m ^k−1) and for which k-rowed F we have that forb(m,F) is Θ(m ^k ).     

Small Forbidden Configurations IV: The 3 Rowed Case

The present paper continues the work begun by Anstee, Griggs and Sali on small forbidden configurations. We define a matrix to be simple if it is a (0,1)-matrix with no repeated columns. Let F be a k×l (0,1)-matrix (the forbidden configuration). Small refers to the size of k and in this paper k = 3. Assume A is an m×n simple matrix which has no submatrix which is a row and column permutation of F. We define forb(m,F) as the best possible upper bound on n, for such a matrix A, which depends on m and F. We complete the classification for all 3-rowed (0,1)-matrices of forb (m,F) as either Θ(m), Θ(m²) or Θ(m³) (with constants depending on F). * Research is supported in part by NSERC. † Research was done while the second author visited the University of British Columbia supported by NSERC of first author. Research was partially supported by Hungarian National Research Fund (OTKA) numbers T034702 and T037846.     

Forbidden Configurations and Product Constructions

A simple matrix is a (0,1)-matrix with no repeated columns. For a (0,1)-matrix F, we say that a (0,1)-matrix A has F as a configuration if there is a submatrix of A which is a row and column permutation of F (trace is the set system version of a configuration). Let \({\|A\|}\) denote the number of columns of A. We define \({{\rm forb}(m, F) = {\rm max}\{\|A\| \,:\, A}\) is m-rowed simple matrix and has no configuration F. We extend this to a family \({\mathcal{F} = \{F_1, F_2, \ldots , F_t\}}\) and define \({{\rm forb}(m, \mathcal{F}) = {\rm max}\{\|A\| \,:\, A}\) is m-rowed simple matrix and has no configuration \({F \in \mathcal{F}\}}\) . We consider products of matrices. Given an m ₁ × n ₁ matrix A and an m ₂ × n ₂ matrix B, we define the product A × B as the (m ₁ + m ₂) × n ₁ n ₂ matrix whose columns consist of all possible combinations obtained from placing a column of A on top of a column of B. Let I _k denote the k × k identity matrix, let \({I_k^{c}}\) denote the (0,1)-complement of I _k and let T _k denote the k × k upper triangular (0,1)-matrix with a 1 in position i, j if and only if i ≤ j. We show forb(m, {I ₂ × I ₂, T ₂ × T ₂}) is \({\Theta(m^{3/2})}\) while obtaining a linear bound when forbidding all 2-fold products of all 2 × 2 (0,1)-simple matrices. For two matrices F, P, where P is m-rowed, let \({f(F, P) = {\rm max}_{A} \{\|A\| \,:\,A}\) is m-rowed submatrix of P with no configuration F}. We establish f(I ₂ × I ₂, I _m/2 × I _m/2) is \({\Theta(m^{3/2})}\) whereas f(I ₂ × T ₂, I _m/2 × T _m/2) and f(T ₂ × T ₂, T _m/2 × T _m/2) are both \({\Theta(m)}\) . Additional results are obtained. One of the results requires extensive use of a computer program. We use the results on patterns due to Marcus and Tardos and generalizations due to Klazar and Marcus, Balogh, Bollobás and Morris.     

Forbidden configurations and repeated induction

For a given k×? matrix F, we say a matrix A has no configurationF if no k×? submatrix of A is a row and column permutation of F. We say a matrix is simple if it is a (0,1)-matrix with no repeated columns. We define as the maximum number of columns in an m-rowed simple matrix which has no configuration F. A fundamental result of Sauer, Perles and Shelah, and Vapnik and Chervonenkis determines exactly, where K_k denotes the k×2^k simple matrix. We extend this in several ways. For two matrices G,H on the same number of rows, let [G∣H] denote the concatenation of G and H. Our first two sets of results are exact bounds that find some matrices B,C where and . Our final result provides asymptotic boundary cases; namely matrices F for which is O(m^p) yet for any choice of column α not in F, we have is Ω(m^p+1). This is evidence for a conjecture of Anstee and Sali. The proof techniques in this paper are dominated by repeated use of the standard induction employed in forbidden configurations. Analysis of base cases tends to dominate the arguments. For a k-rowed (0,1)-matrix F, we also consider a function which is the minimum number of columns in an m-rowed simple matrix for which each k-set of rows contains F as a configuration.     

Forbidden submatrices

We consider a m × n (0, 1)-matrix A, no repeated columns, which has no k × l sumatrix F. We may deduce bounds on n, polynomial in m, depending on F. The best general bound is O(m^2k−1). We improve this and provide best possible bounds for k × 1 F's and certain k × 2 F's. In the case that all columns of F are the same, good bounds are obtained which are best possible for l = 2 and some other cases. Good bounds for 1 × l F's are provided, namely n ⩽ (l−1)m + 1, which are shown to be best possible for F = [1010...10]. The paper finishes with a study of the 14 different 3 × 2 possibilities for F, solving all but 3.     

Removable matchings and hamiltonian cycles

For a graph G, let σ₂(G) denote the minimum degree sum of two nonadjacent vertices (when G is complete, we let σ₂(G)=∞). In this paper, we show the following two results: (i) Let G be a graph of order n≥4k+3 with σ₂(G)≥n and let F be a matching of size k in G such that G−F is 2-connected. Then G−F is hamiltonian or G≅K₂+(K₂∪K_n−4) or ; (ii) Let G be a graph of order n≥16k+1 with σ₂(G)≥n and let F be a set of k edges of G such that G−F is hamiltonian. Then G−F is either pancyclic or bipartite. Examples show that first result is the best possible.     

On “P” property and the column-W property

P-matrices play an important role in the well-posedness of a linear complementarity problem (LCP). Similarly, the well-posedness of a horizontal linear complementarity problem (HLCP) is closely related to the column-W property of a matrix k-tuple.In this paper we first consider the problem of generating P-matrices from a given pair of matrices. Given a matrix pair (D, F) where D is a square matrix of order m and matrix F has m rows, “what are the conditions under which there exists a matrix G such that (D + FG) is a P-matrix?”. We obtain necessary and sufficient conditions for the special case when the column rank of F is m ? 1. A decision algorithm of complexity O(m²) to check whether the given pair of matrices (D, F) is P-matrisable is obtained. We also obtain a necessary and an independent sufficient condition for the general case when rank(F) is less than m ? 1.We then generalise the P-matrix generating problem to the generation of matrix k-tuples satisfying the column-W property from a given matrix (k + 1)-tuple. That is, given a matrix (k + 1)-tuple (D₁, … ,D_k, F), where D_js are square matrices of order m and F is a matrix having m rows, we determine the conditions under which the matrix k-tuple (D₁ + FG₁, … ,D_k + FG_k) satisfies the column-W property. As in the case of P-matrices we obtain necessary and sufficient conditions for the case when rank(F) = m ? 1. Using these conditions a decision algorithm of complexity O(km²) to check whether the given matrix (k + 1)-tuple is column-W matrisable is obtained. Then for the case when rank(F) is less than m ? 1, we obtain a necessary and an independent sufficient condition.For a special sub-class of P-matrices we give a polynomial time decision algorithm for P-matrisability. Finally, we obtain a geometric characterisation of column-W property by generalising the well known separation theorem for P-matrices.     

Compositions of Polynomials with Coefficients in a Given Field

Let F ⊂ K be fields of characteristic 0, and let K[x] denote the ring of polynomials with coefficients in K. Let p(x) = ∑_k = 0ⁿa_kx^k ∈ K[x], a_n ≠ 0. For p ∈ K[x]\F[x], define D_F(p), the F deficit of p, to equal n − max{0 ≤ k ≤ n : a_k∉F}. For p ∈ F[x], define D_F(p) = n. Let p(x) = ∑_k = 0ⁿa_kx^k and let q(x) = ∑_j = 0^mb_jx^j, with a_n ≠ 0, b_m ≠ 0, a_n, b_m ∈ F, b_j∉F for some j ≥ 1. Suppose that p ∈ K[x], q ∈ K[x]\F[x], p, not constant. Our main result is that p ° q ∉ F[x] and D_F(p ° q) = D_F(q). With only the assumption that a_nb_m ∈ F, we prove the inequality D_F(p ° q) ≥ D_F(q). This inequality also holds if F and K are only rings. Similar results are proven for fields of finite characteristic with the additional assumption that the characteristic of the field does not divide the degree of p. Finally we extend our results to polynomials in two variables and compositions of the form p(q(x, y)), where p is a polynomial in one variable.     

The least degree of identities in the subspace M 1 (m,k) (F) of the matrix superalgebra M (m,k)(F)

We determine the least degree of identities in the subspace M ₁ ^(m,k) (F) of the matrix superalgebra M ^(m,k)(F) over a field F for arbitrary m and k. For the subspace M ₁ ^(m,k) (F) (k > 1) we obtain concrete minimal identities and generalize some results by Chang and Domokos.     

On polyvectors of vector spaces and hyperplanes of projective Grassmannians

We investigate relationships between polyvectors of a vector space V, alternating multilinear forms on V, hyperplanes of projective Grassmannians and regular spreads of projective spaces. Suppose V is an n-dimensional vector space over a field F and that A_n-1,k(F) is the Grassmannian of the (k − 1)-dimensional subspaces of PG(V) (1  ? k ? n − 1). With each hyperplane H of A_n-1,k(F), we associate an (n − k)-vector of V (i.e., a vector of ∧^n−kV) which we will call a representative vector of H. One of the problems which we consider is the isomorphism problem of hyperplanes of A_n-1,k(F), i.e., how isomorphism of hyperplanes can be recognized in terms of their representative vectors. Special attention is paid here to the case n = 2k and to those isomorphisms which arise from dualities of PG(V). We also prove that with each regular spread of the projective space PG(2k-1,F), there is associated some class of isomorphic hyperplanes of the Grassmannian A_2k-1,k(F), and we study some properties of these hyperplanes. The above investigations allow us to obtain a new proof for the classification, up to equivalence, of the trivectors of a 6-dimensional vector space over an arbitrary field F, and to obtain a classification, up to isomorphism, of all hyperplanes of A_5,3(F).     

Some estimations for the least degree of identities of subspaces M1(m,k) (F) of the matrix superalgebra M(m,k)(F)

We estimate the least degree of identities of subspaces M ₁^(m,k) (F) of the matrix superalgebra M ^(m,k)(F) over the field F for arbitrary m and k. For subspaces M ₁^(m,1) (F) (m≥1) and M ₁^(2,2) (F) we obtain concrete minimal identities.     

Uniformly optimal graphs in some classes of graphs with node failures

The uniformly optimal graph problem with node failures consists of finding the most reliable graph in the class Ω(n,m) of all graphs with n nodes and m edges in which nodes fail independently and edges never fail. The graph G is called uniformly optimal in Ω(n,m) if, for all node-failure probabilities q∈(0,1), the graph G is the most reliable graph in the class of graphs Ω(n,m). This paper proves that the multipartite graphs K(b,b+1,…,b+1,b+2) are uniformly optimal in their classes Ω((k+2)(b+1),(k²+3k+2)(b+1)²/2−1), where k is the number of partite sets of size (b+1), while for i>2, the multipartite graphs K(b,b+1,…,b+1,b+i) are not uniformly optimal in their classes Ω((k+2)b+k+i,(k+2)(k+1)b²/2+(k+1)(k+i)b+k(k+2i−1)/2).     

Decomposition of bipartite graphs into special subgraphs

Let F and G be two graphs and let H be a subgraph of G. A decomposition of G into subgraphs F₁,F₂,…,F_m is called an F-factorization of G orthogonal to H if F_i≅F and |E(F_i∩H)|=1 for each i=1,2,…,m. Gyárfás and Schelp conjectured that the complete bipartite graph K_4k,4k has a C₄-factorization orthogonal to H provided that H is a k-factor of K_4k,4k. In this paper, we show that (1) the conjecture is true when H satisfies some structural conditions; (2) for any two positive integers r?k, K_kr²,kr² has a K_r,r-factorization orthogonal to H if H is a k-factor of K_kr²,kr²; (3) K_2d²,2d² has a C₄-factorization such that each edge of H belongs to a different C₄ if H is a subgraph of K_2d²,2d² with maximum degree Δ(H)?d.     

Maximal exponents of polyhedral cones (I)

Let K be a proper (i.e., closed, pointed, full convex) cone in Rn. An n×n matrix A is said to be K-primitive if there exists a positive integer k such that ; the least such k is referred to as the exponent of A and is denoted by γ(A). For a polyhedral cone K, the maximum value of γ(A), taken over all K-primitive matrices A, is called the exponent of K and is denoted by γ(K). It is proved that if K is an n-dimensional polyhedral cone with m extreme rays then for any K-primitive matrix A, γ(A)?(mA−1)(m−1)+1, where mA denotes the degree of the minimal polynomial of A, and the equality holds only if the digraph (E,P(A,K)) associated with A (as a cone-preserving map) is equal to the unique (up to isomorphism) usual digraph associated with an m×m primitive matrix whose exponent attains Wielandt's classical sharp bound. As a consequence, for any n-dimensional polyhedral cone K with m extreme rays, γ(K)?(n−1)(m−1)+1. Our work answers in the affirmative a conjecture posed by Steve Kirkland about an upper bound of γ(K) for a polyhedral cone K with a given number of extreme rays.     

Perfect Matchings and K 4 3 -Tilings in Hypergraphs of Large Codegree

For a k-graph F, let t _l (n, m, F) be the smallest integer t such that every k-graph G on n vertices in which every l-set of vertices is included in at least t edges contains a collection of vertex-disjoint F-subgraphs covering all but at most m vertices of G. Let K _m ^k denote the complete k-graph on m vertices. The function $t_{k-1} (kn, 0, K_k^k)For a k-graph F, let t _l (n, m, F) be the smallest integer t such that every k-graph G on n vertices in which every l-set of vertices is included in at least t edges contains a collection of vertex-disjoint F-subgraphs covering all but at most m vertices of G. Let K _m ^k denote the complete k-graph on m vertices. The function (i.e. when we want to guarantee a perfect matching) has been previously determined by Kühn and Osthus [9] (asymptotically) and by R?dl, Ruciński, and Szemerédi [13] (exactly). Here we obtain asymptotic formulae for some other l. Namely, we prove that for any and , . Also, we present various bounds in another special but interesting case: t ₂(n, m, K ₄³) with m = 0 or m = o(n), that is, when we want to tile (almost) all vertices by copies of K ₄³, the complete 3-graph on 4 vertices. Reverts to public domain 28 years from publication. Oleg Pikhurko: Partially supported by the National Science Foundation, Grant DMS-0457512.     

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.     

On the chromaticity of complete multipartite graphs with certain edges added

Let P(G,λ) be the chromatic polynomial of a graph G. A graph G is chromatically unique if for any graph H, P(H,λ)=P(G,λ) implies H is isomorphic to G. For integers k≥0, t≥2, denote by K((t−1)×p,p+k) the complete t-partite graph that has t−1 partite sets of size p and one partite set of size p+k. Let K(s,t,p,k) be the set of graphs obtained from K((t−1)×p,p+k) by adding a set S of s edges to the partite set of size p+k such that 〈S〉 is bipartite. If s=1, denote the only graph in K(s,t,p,k) by K⁺((t−1)×p,p+k). In this paper, we shall prove that for k=0,1 and p+k≥s+2, each graph G∈K(s,t,p,k) is chromatically unique if and only if 〈S〉 is a chromatically unique graph that has no cut-vertex. As a direct consequence, the graph K⁺((t−1)×p,p+k) is chromatically unique for k=0,1 and p+k≥3.     

Multiple partitions, lattice paths and a Burge-Bressoud-type correspondence

A bijection is presented between (1): partitions with conditions f_j+f_j+1≤k−1 and f₁≤i−1, where f_j is the frequency of the part j in the partition, and (2): sets of k−1 ordered partitions (n⁽¹⁾,n⁽²⁾,…,n^(k−1)) such that and , where m_j is the number of parts in n^(j). This bijection entails an elementary and constructive proof of the Andrews multiple-sum enumerating partitions with frequency conditions. A very natural relation between the k−1 ordered partitions and restricted paths is also presented, which reveals our bijection to be a modification of Bressoud’s version of the Burge correspondence.     

General forbidden configuration theorems

Results in this paper gives bounds on the number of columns in a matrix when certain submatrices are forbidden. Let F be a k by l (0, 1)-matrix with no repeated columns, column sums at least s. Let A be a m by n (0, 1)-matrix with no repeated column, column sums at least s and no submatrix F nor any row and column permutation of F. Then $\text{n?(}\text{m}\text{k?1}\text{) + (}\text{m}\text{k?2}\text{) + ? + (}\text{m}\text{s}\text{)}$. This bound is best possible for numerous F. The bound, with s = 0, is an easy corollary to a bound of Sauer and Perles and Shelah. The bounds can be extended to any F and to any F where we do not allow row and column permutations. The results follow from a configuration theorem that says, in essence, that matrices without a configuration are determined by row intersections of sets of rows of various sizes. A linear independence argument yields the bound. Results of Ryser, Frankl and Pach, Quinn and the author are obtained.