Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEncoding labelled $p$-Riordan graphs by words and pattern-avoiding permutations
93
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
The notion of a $p$-Riordan graph generalizes that of a Riordan graph, which, in turn, generalizes the notions of a Pascal graph and a Toeplitz graph. In this paper we introduce the notion of a $p$-Riordan word, and show how to encode $p$-Riordan graphs by $p$-Riordan words. For special important cases of Riordan graphs (the case $p=2$) and oriented Riordan graphs (the case $p=3$) we provide alternative encodings in terms of pattern-avoiding permutations and certain balanced words, respectively. As a bi-product of our studies, we provide an alternative proof of a known enumerative result on closed walks in the cube.
rate research
Read More
An alternating permutation of length $n$ is a permutation $pi=pi_1 pi_2 ... pi_n$ such that $pi_1 < pi_2 > pi_3 < pi_4 > ...$. Let $A_n$ denote set of alternating permutations of ${1,2,..., n}$, and let $A_n(sigma)$ be set of alternating permutations in $A_n$ that avoid a pattern $sigma$. Recently, Lewis used generating trees to enumerate $A_{2n}(1234)$, $A_{2n}(2143)$ and $A_{2n+1}(2143)$, and he posed several conjectures on the Wilf-equivalence of alternating permutations avoiding certain patterns. Some of these conjectures have been proved by Bona, Xu and Yan. In this paper, we prove the two relations $|A_{2n+1}(1243)|=|A_{2n+1}(2143)|$ and $|A_{2n}(4312)|=|A_{2n}(1234)|$ as conjectured by Lewis.
Babson and Steingr{i}msson introduced generalized permutation patterns and showed that most of the Mahonian statistics in the literature can be expressed by the combination of generalized pattern functions. Particularly, they defined a new Mahonian statistic in terms of generalized pattern functions, which is denoted $stat$. Recently, Amini investigated the equidistributions of these Mahonian statistics over sets of pattern avoiding permutations. Moreover, he posed several conjectures. In this paper, we construct a bijection from $S_n(213)$ to $S_n(231)$, which maps the statistic $(maj,stat)$ to the statistic $(stat,maj)$. This allows us to give solutions to some of Aminis conjectures.
A permutation $sigmainmathfrak{S}_n$ is simsun if for all $k$, the subword of $sigma$ restricted to ${1,...,k}$ does not have three consecutive decreasing elements. The permutation $sigma$ is double simsun if both $sigma$ and $sigma^{-1}$ are simsun. In this paper we present a new bijection between simsun permutations and increasing 1-2 trees, and show a number of interesting consequences of this bijection in the enumeration of pattern-avoiding simsun and double simsun permutations. We also enumerate the double simsun permutations that avoid each pattern of length three.
There is a long line of research in the literature dedicated to word-representable graphs, which generalize several important classes of graphs. However, not much is known about word-representability of split graphs, another important class of graphs. In this paper, we show that threshold graphs, a subclass of split graphs, are word-representable. Further, we prove a number of general theorems on word-representable split graphs, and use them to characterize computationally such graphs with cliques of size 5 in terms of 9 forbidden subgraphs, thus extending the known characterization for word-representable split graphs with cliques of size 4. Moreover, we use split graphs, and also provide an alternative solution, to show that gluing two word-representable graphs in any clique of size at least 2 may, or may not, result in a word-representable graph. The two surprisingly simple solutions provided by us answer a question that was open for about ten years.
In this paper we study the enumeration and the construction, according to the number of ones, of particular binary words avoiding a fixed pattern. The growth of such words can be described by particular jumping and marked succession rules. This approach enables us to obtain an algorithm which constructs all binary words having a fixed number of ones and then kills those containing the forbidden pattern.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
