Pattern avoidance for alternating permutations and Young tableaux

We define a class Ln,k of permutations that generalizes alternating (up-down) permutations and give bijective proofs of certain pattern-avoidance results for this class. As a special case of our results, we give bijections between the set A2n(1234) of alternating permutations of length 2n with no four-term increasing subsequence and standard Young tableaux of shape 〈n³〉, and between the set A2n+1(1234) and standard Young tableaux of shape 〈³n−1,2,1〉. This represents the first enumeration of alternating permutations avoiding a pattern of length four. We also extend previous work on doubly-alternating permutations (alternating permutations whose inverses are alternating) to our more general context.The set Ln,k may be viewed as the set of reading words of the standard Young tableaux of a certain skew shape. In the last section of the paper, we expand our study to consider pattern avoidance in the reading words of standard Young tableaux of any skew shape. We show bijectively that the number of standard Young tableaux of shape λ/μ whose reading words avoid 213 is a natural μ-analogue of the Catalan numbers (and in particular does not depend on λ, up to a simple technical condition), and that there are similar results for the patterns 132, 231 and 312.     

Enumeration of rooted nonseparable outerplanar maps

In this paper, the number of combinatorially distinct rooted nonseparable outerplanar maps withm edges and the valency of the root-face being n is found to be(m-1)! (m-2) !:(n-1)!(n-2)! (m-n)!(m-n 1)!and, the number of rooted nonseparable outerplanar maps with m edges is also determined to be(2m-2)!:(m-1)!m!,which is just the number of distinct rooted plane trees with m-1 edges.     

Baxter permutations

Chung et al. (1978) have proved that the number of Baxter permutations on [n] is

Viennot (1981) has then given a combinatorial proof of this formula, showing this sum corresponds to the distribution of these permutations according to their number of rises.

Cori et al. (1986), by making a correspondence between two families of planar maps, have shown that the number of alternating Baxter permutations on [2n+δ] is c_n+δc_n where c_n = (2n)!/(n + 1)!n! is the nth Catalan number.

In this paper, we establish a new one-to-one correspondence between Baxter permutations and three non-intersecting paths, which unifies Viennot (1981) and Cori et al. (1986). Moreover, we obtain more precise results for the enumeration of (alternating or not) Baxter permutations according to various parameters. So, we give a combinatorial interpretation of Mallows's formula (1979).     

Commutativity preserving linear maps and Lie automorphisms of strictly triangular matrix space

In this paper we classify linear maps preserving commutativity in both directions on the space N(F) of strictly upper triangular (n+1)×(n+1) matrices over a field F. We show that for n3 a linear map on N(F) preserves commutativity in both directions if and only if =^′+f where ^′ is a product of standard maps on N(F) and f is a linear map of N(F) into its center.     

Coloring permutation graphs in parallel

A coloring of a graph G is an assignment of colors to its vertices so that no two adjacent vertices have the same color. We study the problem of coloring permutation graphs using certain properties of the lattice representation of a permutation and relationships between permutations, directed acyclic graphs and rooted trees having specific key properties. We propose an efficient parallel algorithm which colors an n-node permutation graph in O(log² n) time using O(n²/log n) processors on the CREW PRAM model. Specifically, given a permutation π we construct a tree T^*[π], which we call coloring-permutation tree, using certain combinatorial properties of π. We show that the problem of coloring a permutation graph is equivalent to finding vertex levels in the coloring-permutation tree.     

Label placement by maximum independent set in rectangles

Motivated by the problem of labeling maps, we investigate the problem of computing a large non-intersecting subset in a set of n rectangles in the plane. Our results are as follows. In O(n log n) time, we can find an O(log n)-factor approximation of the maximum subset in a set of n arbitrary axis-parallel rectangles in the plane. If all rectangles have unit height, we can find a 2-approximation in O(n log n) time. Extending this result, we obtain a (1 + 1/k)-approximation in time O(n log n + n^2k−1) time, for any integer k ≥ 1.     

Evacuation and a geometric construction for Fibonacci tableaux

Tableaux have long been used to study combinatorial properties of permutations and multiset permutations. Discovered independently by Robinson and Schensted and generalized by Knuth, the Robinson–Schensted correspondence has provided a fundamental tool for relating permutations to tableaux. In 1963, Schützenberger defined a process called evacuation on standard tableaux which gives a relationship between the pairs of tableaux (P,Q) resulting from the Schensted correspondence for a permutation and both the reverse and the complement of that permutation. Viennot gave a geometric construction for the Schensted correspondence and Fomin described a generalization of the correspondence which provides a bijection between permutations and pairs of chains in Young's lattice.In 1975, Stanley defined a Fibonacci lattice and in 1988 he introduced the idea of a differential poset. Roby gave an insertion algorithm, analogous to the Schensted correspondence, for mapping a permutation to a pair of Fibonacci tableaux. The main results of this paper are to give an evacuation algorithm for the Fibonacci tableaux that is analogous to the evacuation algorithm on Young tableaux and to describe a geometric construction for the Fibonacci tableaux that is similar to Viennot's geometric construction for Young tableaux.     

Short permutation strings

A permutation string is a string of symbols over the numerals 1, 2, …, n such that all permutations of the string 1 2 … n are subsequences. The search for short permutation strings arose out of studies into the complexity of shortest path algorithms by Karp and others. The results in the sequel are presented independent of such studies because they are felt to be of intrinsic combinatorial interest [1]. An algorithm for constructing permutation strings of length n²−2n+4 is given.     

Enumeration on Nonseparable Planar Maps

This paper provides some functional equations satisfied by the generating functions for nonseparable rooted planar maps with the valency of root-vertex, the number of edges and the valency of root-faces of the maps as three parameters. But the solutions of these equations can only be obtained indirectly by considering some relations between nonseparable and general rooted planar maps. One of them is an answer to the open problem 6.1 in Liu (1983, Comb. Optim. CORR83-26, University of Waterloo).     

Les hypercartes planaires sont des arbres tres bien etiquetes

R. Cori and B. Vauquelin have constructed (cf[1]) a one to one correspondence from rooted planar maps onto rooted well-labeled trees (trees whose vertices are labeled with natural numbers that differ by at most one on adjacent vertices). This correspondence does not associate other families of planar maps (e.g. planar hypermaps,...) and easily definable families of trees. The main result of this paper (Theorem 1, Section II) is to construct a new one to one correspondence from rooted planar maps onto rooted well-labeled trees which also associates rooted planar hypermaps with n edge-ends (called ‘brin’ in French) and rooted very well-labeled trees (well labeled trees whose adjacent vertices have not the same label) with n edges. This last result is given in Section 3, Theorem 2.The coding of rooting very well-labeled trees by words extending Dyck's words (or parenthesis systems), allows their enumeration, hence the enumeration of rooted planar hypermaps. This side is the subject of a work in progress under B. Vauquelin.     

Enumeration of irreducible binary words

Overlap free words over two letters are called irreducible binary words. Let d(n) denote the number of irreducible binary words of length n. In this paper we show that there are positive constants C₁ and C₂ such that C₁n^1.155<d(n)<C₂n^1.587 holds for all n>0.     

Computing rectangle enclosures

The rectangle enclosure problem is the problem of determining the subset of n iso-oriented planar rectangles that enclose a query rectangle Q. In this paper, we use a three layered data structure which is a combination of Range and Priority search trees and answers both the static and dynamic cases of the problem. Both the cases use O(n> log² n) space. For the static case, the query time is O(log² n log log n + K). The dynamic case is supported in O(log³ n + K) query time using O(log³ n) amortized time per update. K denotes the size of the answer. For the d-dimensional space the results are analogous. The query time is O(log^2d-2 n log log n + K) for the static case and O(log^2d-1 n + K) for the dynamic case. The space used is O(n> log^2d-2 n) and the amortized time for an update is O(log^2d-1 n). The existing bounds given for a class of problems which includes the present one, are O(log^2d n + K) query time, O(log^2d n) time for an insertion and O(log^2d-1 n) time for a deletion.     

Subsets of an interval whose product is a power

We form squares from the product of integers in a short interval [n, n + t_n], where we include n in the product. If p is prime, p|n, and (₂^p) > n, we prove that p is the minimum t_n. If no such prime exists, we prove t_n √5n when n> 32. If n = p(2p − 1) and both p and 2p − 1 are primes, then t_n = 3p> 3 √n/2. For n(n + u) a square > n², we conjecture that a and b exist where n < a < b < n + u and nab is a square (except n = 8 and N = 392). Let g₂(n) be minimal such that a square can be formed as the product of distinct integers from [n, g₂(n)] so that no pair of consecutive integers is omitted. We prove that g₂(n) 3n − 3, and list or conjecture the values of g₂(n) for all n. We describe the generalization to kth powers and conjecture the values for large n.     

Multiplicative properties of generalized matrix functions

We consider scalar-valued matrix functions for n×n matrices A=(a_ij) defined by Where G is a subgroup of S_n the group of permutations on n letters, and χ is a linear character of G. Two such functions are the permanent and the determinant. A function (1) is multiplicative on a semigroup S of n×n matrices if d(AB)=d(A)d(B) AB∈S.

With mild restrictions on the underlying scalar ring we show that every element of a semigroup containing the diagonal matrices on which (1) is multiplicative can have at most one nonzero diagonal(i.e., diagonal with all nonzero entries)and conversely, provided that χ is the principal character(χ≡1).     

Balanced tableaux

We study a new class of tableaux defined by a certain condition on hook-ranks. Many connections with the classical theory of standard Young tableaux are developed, as well as applications to the problem of enumerating reduced decompositions of permutations in S_n.     

Further results on irregular, critical perfect systems of difference sets II: systems without splits

An (m, n; u, v; c)-system is a collection of components, m of valency u−1 and n of valency v−1, whose difference sets form a perfect system with threshold c. If there is an (m, n; 3, 6; c)-system, then m2c−1; and if there is a (2c−1, n; 3, 6; c)-system, then 2c−1n. For all sufficiently large c, there are (2c−1, n; 3, 6; c)-systems with a split at 3c+6n−1 at least when n=1, 5, 6 and 7, but such systems do not exist for n=2, 3 or 4.

We describe here a general method of construction for (2c−1, n; 3, 6; c)-systems and use it to show that there are such systems for 2n4 and certain values of c depending on n. We also discuss the limitations of this method.     

Extending matchings in planar graphs V

A graph G on at least 2n + 2 vertices in n-extendable if every set of n independent edges extends to (i.e., is a subset of) a perfect matching in G. It is known that no planar graph is 3-extendable. In the present paper we continue to study 2-extendability in the plane. Suppose independent edges e₁ and e₂ are such that the removal of their endvertices leaves at least one odd component C_o. The subgraph G[V(C_o) V(e₁) V(e₂)] is called a generalized butterfly (or gbutterfly). Clearly, a 2-extendable graph can contain no gbutterfly. The converse, however, is false.

We improve upon a previous result by proving that if G is 4-connected, locally connected and planar with an even number of vertices and has no gbutterfly, it is 2-extendable. Sharpness with respect to the various hypotheses of this result is discussed.     

On the multisearching problem for hypercubes

In this paper we give improved bounds for the multisearch problem on a hypercube. This is a parallel search problem where the elements in the structure S to be searched are totally ordered, but where it is not possible to compare in constant time any two given queries q and q′. More precisely, we are given on a n-processor hypercube a sorted n-element sequence S, and a set Q of n queries, and we need to find for each query q Q its location in the sorted S. We present an improved algorithm for the multisearch problem, one that takes O(log n(log log n)³) time on a n-processor hypercube. This problem is fundamental in computational geometry, for example it models planar point location in a slab. We give as application a trapezoidal decomposition algorithm with the same time complexity on a n log n-processor hypercube. The hypercube model for which we claim our bounds is the standard one, SIMD, with O(1) memory registers per processor, and with one-port communication. Each register can store O(log n) bits, so that a processor knows its ID.     

An inequality for M-matrices

If AB are n × n M matrices with dominant principal diagonal, we show that 3[det(A + B)]^1/n ≥ (det A)^1/n + (det B)^1/n.