Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn a conjecture of Lin and Kim concerning a refinement of Schroder numbers
466
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In this paper, we compute the distribution of the first letter statistic on nine avoidance classes of permutations corresponding to two pairs of patterns of length four. In particular, we show that the distribution is the same for each class and is given by the entries of a new Schroder number triangle. This answers in the affirmative a recent conjecture of Lin and Kim. We employ a variety of techniques to prove our results, including generating trees, direct bijections and the kernel method. For the latter, we make use of in a creative way what we are trying to show in three cases to aid in solving a system of functional equations satisfied by the associated generating functions.
rate research
Read More
Let $r(n,k)$ (resp. $s(n,k)$) be the number of Schroder paths (resp. little Schroder paths) of length $2n$ with $k$ hills, and set $r(0,0)=s(0,0)=1$. We bijectively establish the following recurrence relations: begin{align*} r(n,0)&=sumlimits_{j=0}^{n-1}2^{j}r(n-1,j), r(n,k)&=r(n-1,k-1)+sumlimits_{j=k}^{n-1}2^{j-k}r(n-1,j),quad 1le kle n, s(n,0) &=sumlimits_{j=1}^{n-1}2cdot3^{j-1}s(n-1,j), s(n,k) &=s(n-1,k-1)+sumlimits_{j=k+1}^{n-1}2cdot3^{j-k-1}s(n-1,j),quad 1le kle n. end{align*} The infinite lower triangular matrices $[r(n,k)]_{n,kge 0}$ and $[s(n,k)]_{n,kge 0}$, whose row sums produce the large and little Schroder numbers respectively, are two Riordan arrays of Bell type. Hence the above recurrences can also be deduced from their $A$- and $Z$-sequences characterizations. On the other hand, it is well-known that the large Schroder numbers also enumerate separable permutations. This propelled us to reveal the connection with a lesser-known permutation statistic, called initial ascending run, whose distribution on separable permutations is shown to be given by $[r(n,k)]_{n,kge 0}$ as well.
Let $G=(V(G), E(G))$ be a multigraph with maximum degree $Delta(G)$, chromatic index $chi(G)$ and total chromatic number $chi(G)$. The Total Coloring conjecture proposed by Behzad and Vizing, independently, states that $chi(G)leq Delta(G)+mu(G) +1$ for a multigraph $G$, where $mu(G)$ is the multiplicity of $G$. Moreover, Goldberg conjectured that $chi(G)=chi(G)$ if $chi(G)geq Delta(G)+3$ and noticed the conjecture holds when $G$ is an edge-chromatic critical graph. By assuming the Goldberg-Seymour conjecture, we show that $chi(G)=chi(G)$ if $chi(G)geq max{ Delta(G)+2, |V(G)|+1}$ in this note. Consequently, $chi(G) = chi(G)$ if $chi(G) ge Delta(G) +2$ and $G$ has a spanning edge-chromatic critical subgraph.
We study the generating function of descent numbers for the permutations with descent pairs of prescribed parities, the distribution of which turns out to be a refinement of median Genocchi numbers. We prove the $gamma$-positivity for the polynomial and derive the generating function for the $gamma$-vectors, expressed in the form of continued fraction. We also come up with an artificial statistic that gives a $q$-analogue of the $gamma$-positivity for the permutations with descents only allowed from an odd value to an odd value.
There is a bijection from Schroder paths to {4132, 4231}-avoiding permutations due to Bandlow, Egge, and Killpatrick that sends area to inversion number. Here we give a concise description of this bijection.
Karasev conjectured that for any set of $3k$ lines in general position in the plane, which is partitioned into $3$ color classes of equal size $k$, the set can be partitioned into $k$ colorful 3-subsets such that all the triangles formed by the subsets have a point in common. Although the general conjecture is false, we show that Karasevs conjecture is true for lines in convex position. We also discuss possible generalizations of this result.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
