Wilfs Sixth Unsolved Problem asks for any interesting properties of the set of partitions of integers for which the (nonzero) multiplicities of the parts are all different. We refer to these as emph{Wilf partitions}. Using $f(n)$ to denote the number of Wilf partitions, we establish lead-order asymptotics for $ln{f(n)}$.
We launch a systematic study of the refined Wilf-equivalences by the statistics $mathsf{comp}$ and $mathsf{iar}$, where $mathsf{comp}(pi)$ and $mathsf{iar}(pi)$ are the number of components and the length of the initial ascending run of a permutation $pi$, respectively. As Comtet was the first one to consider the statistic $mathsf{comp}$ in his book {em Analyse combinatoire}, any statistic equidistributed with $mathsf{comp}$ over a class of permutations is called by us a {em Comtet statistic} over such class. This work is motivated by a triple equidistribution result of Rubey on $321$-avoiding permutations, and a recent result of the first and third authors that $mathsf{iar}$ is a Comtet statistic over separable permutations. Some highlights of our results are: (1) Bijective proofs of the symmetry of the double Comtet distribution $(mathsf{comp},mathsf{iar})$ over several Catalan and Schroder classes, preserving the values of the left-to-right maxima. (2) A complete classification of $mathsf{comp}$- and $mathsf{iar}$-Wilf-equivalences for length $3$ patterns and pairs of length $3$ patterns. Calculations of the $(mathsf{des},mathsf{iar},mathsf{comp})$ generating functions over these pattern avoiding classes and separable permutations. (3) A further refinement by the Comtet statistic $mathsf{iar}$, of Wangs recent descent-double descent-Wilf equivalence between separable permutations and $(2413,4213)$-avoiding permutations.
Amdeberhan conjectured that the number of $(s,s+2)$-core partitions with distinct parts for an odd integer $s$ is $2^{s-1}$. This conjecture was first proved by Yan, Qin, Jin and Zhou, then subsequently by Zaleski and Zeilberger. Since the formula for the number of such core partitions is so simple one can hope for a bijective proof. We give the first direct bijective proof of this fact by establishing a bijection between the set of $(s, s+2)$-core partitions with distinct parts and a set of lattice paths.
For $n > 2k geq 4$ we consider intersecting families $mathcal F$ consisting of $k$-subsets of ${1, 2, ldots, n}$. Let $mathcal I(mathcal F)$ denote the family of all distinct intersections $F cap F$, $F eq F$ and $F, Fin mathcal F$. Let $mathcal A$ consist of the $k$-sets $A$ satisfying $|A cap {1, 2, 3}| geq 2$. We prove that for $n geq 50 k^2$ $|mathcal I(mathcal F)|$ is maximized by $mathcal A$.
For positive integers $w$ and $k$, two vectors $A$ and $B$ from $mathbb{Z}^w$ are called $k$-crossing if there are two coordinates $i$ and $j$ such that $A[i]-B[i]geq k$ and $B[j]-A[j]geq k$. What is the maximum size of a family of pairwise $1$-crossing and pairwise non-$k$-crossing vectors in $mathbb{Z}^w$? We state a conjecture that the answer is $k^{w-1}$. We prove the conjecture for $wleq 3$ and provide weaker upper bounds for $wgeq 4$. Also, for all $k$ and $w$, we construct several quite different examples of families of desired size $k^{w-1}$. This research is motivated by a natural question concerning the width of the lattice of maximum antichains of a partially ordered set.
Szemeredis Regularity Lemma is a very useful tool of extremal combinatorics. Recently, several refinements of this seminal result were obtained for special, more structured classes of graphs. We survey these results in their rich combinatorial context. In particular, we stress the link to the theory of (structural) sparsity, which leads to alternative proofs, refinements and solutions of open problems. It is interesting to note that many of these classes present challenging problems. Nevertheless, from the point of view of regularity lemma type statements, they appear as gentle classes.
James Allen Fill
,Svante Janson
,Mark Daniel Ward
.
(2012)
.
"Partitions with Distinct Multiplicities of Parts: On An Unsolved Problem Posed By Herbert Wilf"
.
Mark Daniel Ward
هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا