Ranks of zero patterns and sign patterns

Let F be a field with at least three elements. Zero patterns P such that all matrices over F with pattern P have the same rank are characterized. Similar results are proven for sign patterns. These results are applied to answering two open questions on conditions for formal nonsingularity of a pattern P, as well as to proving a sufficient condition on P such that all matrices over F with pattern P have the same height characteristic.     

Unavoidable patterns

Let Fk denote the family of 2-edge-colored complete graphs on 2k vertices in which one color forms either a clique of order k or two disjoint cliques of order k. Bollobás conjectured that for every ?>0 and positive integer k there is n(k,?) such that every 2-edge-coloring of the complete graph of order n?n(k,?) which has at least edges in each color contains a member of Fk. This conjecture was proved by Cutler and Montágh, who showed that n(k,?)<⁴k/?. We give a much simpler proof of this conjecture which in addition shows that n(k,?)<?−ck for some constant c. This bound is tight up to the constant factor in the exponent for all k and ?. We also discuss similar results for tournaments and hypergraphs.     

Extracting approximate patterns

In this paper, we define a family of patterns with don't cares occurring in a text. We call them primitive patterns. The set of primitive patterns forms a basis for all the maximal patterns occurring in the text. The number of primitive patterns is smaller than other known basis.

We present an incremental algorithm that computes the primitive patterns occurring at least q times in a text of length n, given the N primitive patterns occurring at least q−1 times, in time O(|Σ|Nn²logn), where Σ is the alphabet. In the particular case where q=2, the complexity in time is only O(|Σ|n²logn). We also give an algorithm that decides if a given pattern is primitive in a given text. These algorithms are generalized, taking many sequences in input. Finally, we give a solution for reducing the number of patterns of interest by using scoring techniques, as we show that the number of primitive patterns is exponential.     

Inertially arbitrary patterns

An n×n sign pattern matrix A is an inertially arbitrary pattern (IAP) if each non-negative triple (r s t) with r+s+t=n is the inertia of a matrix with sign pattern A. This paper considers the n×n(n2) skew-symmetric sign pattern S_n with each upper off-diagonal entry positive, the (1,1) entry negative, the (n n) entry positive, and every other diagonal entry zero. We prove that S_n is an IAP.     

Inertially arbitrary patterns

An n×n sign pattern matrix A is an inertially arbitrary pattern (IAP) if each non-negative triple (rst) with r+s+t=n is the inertia of a matrix with sign pattern A. This paper considers the n×n(n≥2) skew-symmetric sign pattern S_n with each upper off-diagonal entry positive, the (1,1) entry negative, the (nn) entry positive, and every other diagonal entry zero. We prove that S_n is an IAP.     

On triangular paperfolding patterns

We introduce patterns on a triangular grid generated by paperfolding operations. We show that in case these patterns are defined using a periodic sequence of foldings, they can also be generated using substitution rules and compute eigenvalues and eigenvectors of the corresponding matrices. We also prove that densities of all basic triangles are equal in these patterns.     

Maximum patterns in datasets

Given a binary dataset of positive and negative observations, a positive (negative) pattern is a subcube having a nonempty intersection with the positive (negative) subset of the dataset, and an empty intersection with the negative (positive) subset of the dataset. Patterns are the key building blocks in Logical Analysis of Data (LAD), and are an essential tool in identifying the positive or negative nature of “new” observations covered by them. We develop exact and heuristic algorithms for constructing a pattern of maximum coverage which includes a given point. It is shown that the heuristically constructed patterns can achieve 81-98% of the maximum possible coverage, while requiring only a fraction of the computing time of the exact algorithm. Maximum patterns are shown to be useful for constructing highly accurate LAD classification models. In comparisons with the commonly used machine learning algorithms implemented in the publicly available Weka software package, the implementation of LAD using maximum patterns is shown to be a highly competitive classification method.     

Shape-Wilf-equivalences for vincular patterns

We extend the notion of shape-Wilf-equivalence to vincular patterns (also known as “generalized patterns” or “dashed patterns”). First we introduce a stronger equivalence on patterns which we call filling-shape-Wilf-equivalence. When vincular patterns α and β   are filling-shape-Wilf-equivalent, we prove that α⊕σ$\alpha \oplus \sigma$ and β⊕σ$\beta \oplus \sigma$ must also be filling-shape-Wilf-equivalent. We also discover two new pairs of patterns which are filling-shape-Wilf-equivalent: when α, β, and σ   are nonempty consecutive patterns which are Wilf-equivalent, α⊕σ$\alpha \oplus \sigma$ is filling-shape-Wilf-equivalent to β⊕σ$\beta \oplus \sigma$; and for any consecutive pattern α  , 1⊕α$1\oplus \alpha$ is filling-shape-Wilf-equivalent to 1?α$1?\alpha$. These new equivalences imply many new Wilf-equivalences for vincular patterns.     

Sparse inertially arbitrary patterns

An n-by-n sign pattern is a matrix with entries in {+,-,0}. An n-by-n nonzero pattern is a matrix with entries in {*,0} where * represents a nonzero entry. A pattern is inertially arbitrary if for every set of nonnegative integers n₁,n₂,n₃ with n₁+n₂+n₃=n there is a real matrix with pattern having inertia (n₁,n₂,n₃). We explore how the inertia of a matrix relates to the signs of the coefficients of its characteristic polynomial and describe the inertias allowed by certain sets of polynomials. This information is useful for describing the inertia of a pattern and can help show a pattern is inertially arbitrary. Britz et al. [T. Britz, J.J. McDonald, D.D. Olesky, P. van den Driessche, Minimal spectrally arbitrary sign patterns, SIAM J. Matrix Anal. Appl. 26 (2004) 257–271] conjectured that irreducible spectrally arbitrary patterns must have at least 2n nonzero entries; we demonstrate that irreducible inertially arbitrary patterns can have less than 2n nonzero entries.     

Spectrally arbitrary ray patterns

An n×n ray pattern A is said to be spectrally arbitrary if for every monic nth degree polynomial f(x) with coefficients from C, there is a matrix in the pattern class of A such that its characteristic polynomial is f(x). In this article the authors extend the nilpotent-Jacobi method for sign patterns to ray patterns, establishing a means to show that an irreducible ray pattern and all its superpatterns are spectrally arbitrary. They use this method to establish that a particular family of n×n irreducible ray patterns with exactly 3n nonzeros is spectrally arbitrary. They then show that every n×n irreducible, spectrally arbitrary ray pattern has at least 3n-1 nonzeros.     

Multi-avoidance of generalised patterns

Recently, Babson and Steingrímsson introduced generalised permutation patterns that allow the requirement that two adjacent letters in a pattern must be adjacent in the permutation. We investigate simultaneous avoidance of two or more 3-patterns without internal dashes, that is, where the pattern corresponds to a contiguous subword in a permutation.     

Packing sets of patterns

Packing density is a permutation occurrence statistic which describes the maximal number of permutations of a given type that can occur in another permutation. In this article we focus on containment of sets of permutations. Although this question has been tangentially considered previously, this is the first article focusing exclusively on it. We find the packing density for various special sets of permutations and study permutation and pattern co-occurrence.     

Enumeration of mapping patterns

Pólya's enumeration theorem is generalized in the following way. We have sets R and D, and a group G acting (by means of representations) on R and D simultaneously. This induces an equivalence relation in the set of all mappings (or of all one-to-one mappings) of R into D. The number of equivalence classes is determined for both cases. The example of types of mappings of a set into itself is treated in detail.     

On random mapping patterns

Random mapping patterns may be represented by unlabelled directed graphs in which each point has out-degree one. We determine the asymptotic behaviour of various parameters associated with such graphs, such as the expected number of points belonging to cycles and the expected number of components. Dedicated to Paul Erdős on his seventieth birthday