On multiple pattern avoiding set partitions

We study classes of set partitions determined by the avoidance of multiple patterns, applying a natural notion of partition containment that has been introduced by Sagan. We say that two sets S and T of patterns are equivalent if for each n the number of partitions of size n avoiding all the members of S is the same as the number of those that avoid all the members of T.     

A major index for matchings and set partitions

We introduce a statistic pmaj(P) for partitions of [n], and show that it is equidistributed with cr₂, the number of 2-crossings, over all partitions of [n] with given sets of minimal block elements and maximal block elements. This generalizes the classical result of equidistribution for the permutation statistics inv and maj.     

Some set partition statistics in non-crossing partitions and generating functions

In this paper we shall give the generating functions for the enumeration of non-crossing partitions according to some set partition statistics explicitly, which are based on whether a block is singleton or not and is inner or outer. Using weighted Motzkin paths, we find the continued fraction form of the generating functions. There are bijections between non-crossing partitions, Dyck paths and non-nesting partitions, hence we can find applications in the enumeration of Dyck paths and non-nesting partitions. We shall also study the integral representation of the enumerating polynomials for our statistics. As an application of integral representation, we shall give some remarks on the enumeration of inner singletons in non-crossing partitions, which is equivalent to one of udu's at high level in Dyck paths investigated in [Y. Sun, The statistic “number of udu's” in Dyck paths, Discrete Math. 284 (2004) 177-186].     

Pattern avoidance in “flattened” partitions

To flatten a set partition (with apologies to Mathematica^®) means to form a permutation by erasing the dividers between its blocks. Of course, the result depends on how the blocks are listed. For the usual listing—increasing entries in each block and blocks arranged in increasing order of their first entries—we count the partitions of [n] whose flattening avoids a single 3-letter pattern. Five counting sequences arise: a null sequence, the powers of 2, the Fibonacci numbers, the Catalan numbers, and the binomial transform of the Catalan numbers.     

On cyclic strings avoiding a pattern

We count the number of cyclic strings over an alphabet that avoid a single pattern under two different assumptions. In the first case, we assume that the symbols of the alphabet are on numbered positions on a circle, while in the second case we assume that the symbols can be freely rotated on the circle (i.e., we deal with necklaces). In each case, we provide a generating function, and we explain how these two cases are related. For the situation of avoiding more than one pattern, we formulate a general conjecture for the first case, and a conditional result for the second case. We also explain the differences between our theory and the theory of Edlin and Zeilberger (2000) by emphasizing how we modified the definition of the enumeration of cyclic strings that avoid one or more patterns when their lengths are less than the length of the longest pattern.     

Bargraph statistics on words and set partitions

In this paper, we consider statistics on partitions of an n-element set represented as a subset of the bargraphs that have n horizontal steps. More precisely, we find the joint distribution of the area and up step statistics on the latter subset of bargraphs, thereby obtaining new refined counts on partitions having a fixed number of blocks. Furthermore, we give explicit formulas in terms of the Stirling numbers for the total area and number of up steps in bargraphs corresponding to partitions, providing both algebraic and combinatorial proofs. Finally, we find asymptotic estimates for the average and total values of these statistics and as a consequence obtain some new identities for the Stirling and Bell numbers.     

Erdős–Ko–Rado theorems for permutations and set partitions

Let Sym([n]) denote the collection of all permutations of [n]={1,…,n}. Suppose is a family of permutations such that any two of its elements (when written in its cycle decomposition) have at least t cycles in common. We prove that for sufficiently large n, with equality if and only if is the stabilizer of t fixed points. Similarly, let denote the collection of all set partitions of [n] and suppose is a family of set partitions such that any two of its elements have at least t blocks in common. It is proved that, for sufficiently large n, with equality if and only if consists of all set partitions with t fixed singletons, where B_n is the nth Bell number.     

On partitions of a partially ordered set

Using linear programming we prove a generalization of Greene and Kleitman's generalization of Dilworth's theorem on the decomposition of a partially ordered set into chains.     

On shortest crucial words avoiding abelian powers

Let k≥2 be an integer. An abeliankth power is a word of the form X₁X₂?X_k where X_i is a permutation of X₁ for 2≤i≤k. A word W is said to be crucial with respect to abelian kth powers if W avoids abelian kth powers, but Wx ends with an abelian kth power for any letter x occurring in W.Evdokimov and Kitaev (2004) [2] have shown that the shortest length of a crucial word on n letters avoiding abelian squares is 4n−7 for n≥3. Furthermore, Glen et al. (2009) [3] proved that this length for abelian cubes is 9n−13 for n≥5. They have also conjectured that for any k≥4 and sufficiently large n, the shortest length of a crucial word on n letters avoiding abelian kth powers, denoted by ?_k(n), is k²n−(k²+k+1). This is currently the best known upper bound for ?_k(n), and the best known lower bound, provided in Glen et al., is 3kn−(4k+1) for n≥5 and k≥4. In this note, we improve this lower bound by proving that for n≥2k−1, ?_k(n)≥k²n−(2k³−3k²+k+1); thus showing that the aforementioned conjecture is true asymptotically (up to a constant term) for growing n.     

On colored set partitions of type B n

Generalizing Reiner’s notion of set partitions of type B _n , we define colored B _n -partitions by coloring the elements in and not in the zero-block respectively. Considering the generating function of colored B _n -partitions, we get the exact formulas for the expectation and variance of the number of non-zero-blocks in a random colored B _n -partition. We find an asymptotic expression of the total number of colored B _n -partitions up to an error of O(n ^?1/2log^7/2 n], and prove that the centralized and normalized number of non-zero-blocks is asymptotic normal over colored B _n -partitions.     

On partitions of K2,3-free graphs under degree constraints

Suppose that $s$, $t$ are two positive integers, and $?$ is a set of graphs. Let $g(s,t;?)$ be the least integer $g$ such that any $?$-free graph with minimum degree at least $g$ can be partitioned into two sets which induced subgraphs have minimum degree at least $s$ and $t$, respectively. For a given graph $H$, we simply write $g(s,t;H)$ for $g(s,t;?)$ when $?=\left\{H\right\}$. In this paper, we show that if $s,t\ge 2$, then $g(s,t;K_{2,3})\le s+t$ and $g(s,t;\{K_3,C_8,K_{2,3}\})\le s+t?1$. Moreover, if $?$ is the set of graphs obtained by connecting a single vertex to exactly two vertices of $K_4?e$, then $g(s,t;?)\le s+t$ on $?$-free graphs with at least five vertices, which generalize a result of Liu and Xu (2017).     

On the complete set packing and set partitioning polytopes: Properties and rank 1 facets

This paper studies two polytopes: the complete set packing and set partitioning polytopes, which are both associated with a binary $n$-row matrix having all possible columns. Cuts of rank 1 for the latter polytope play a central role in recent exact algorithms for many combinatorial problems, such as vehicle routing. We show the precise relation between the two polytopes studied, characterize the multipliers that induce rank 1 clique facets and give several families of multipliers that yield other facets.     

Relations between two types of polarized partitions

It is shown that close links exist between two important types of polarized partition relations of higher dimensions. Project supported by a South-South Fellowship of the Third World Academy of Sciences and by the National Natural Science Foundation of China (Grant No. 19671061).     

On set systems with a threshold property

For n,k and t such that 1<t<k<n, a set F of subsets of [n] has the (k,t)-threshold property if every k-subset of [n] contains at least t sets from F and every (k-1)-subset of [n] contains less than t sets from F. The minimal number of sets in a set system with this property is denoted by m(n,k,t). In this paper we determine m(n,4,3)exactly for n sufficiently large, and we show that m(n,k,2) is asymptotically equal to the generalized Turán number T_k-1(n,k,2).