Nonrationality and Principal permutation classes: the remaining case
We complete the proof of the fact that all principal permutation classes generated by a pattern longer than two have a nonrational generating function.
Researcher profile
Miklos Bona
Miklos Bona contributes to research discovery and scholarly infrastructure.
ResearcherAffiliation not importedOpen to collaborate
Trust snapshot
Quick read
Trust 21 - EmergingVerification L1Unclaimed author
8works
0followers
1topics
2close collaborators
Actions
Decide how to stay connected
Identity and collaboration
How to connect with this researcher
Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.
Log in to claimDirect collaboration
Open a focused conversation when the fit is right
Claim this author entity first to unlock direct invitations.
Research graph
See the researcher in context
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.
Building this graph slice
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
8 published item(s)
preprint2020arXiv
Pattern avoiding permutations and involutions with a unique longest increasing subsequence
We investigate permutations and involutions that avoid a pattern of length three and have a {\em unique} longest increasing subsequence.
0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv
Stack words and a bound for 3-stack sortable permutations
We use stack words to find a new, simple proof for the best known upper bound for the number of 3-stack sortable permutations of a given length. This is the first time that stack words are used to obtain such a result.
0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv
$k$-protected vertices in binary search trees
We show that for every $k$, the probability that a randomly selected vertex of a random binary search tree on $n$ nodes is at distance $k-1$ from the closest leaf converges to a rational constant $c_k$ as $n$ goes to infinity.
0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv
On a Family of Conjectures of Joel Lewis on Alternating Permutations
We prove generalized versions of some conjectures of Joel Lewis on the number of alternating permutations avoiding certain patterns. Our main tool is the perhaps surprising observation that a classic bijection on pattern avoiding permutations often preserves the alternating property.
0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv
On the Best Upper Bound for Permutations Avoiding A Pattern of a Given Length
Numerical evidence suggests that certain permutation patterns of length k are easier to avoid than any other patterns of that same length. We prove that these patterns are avoided by no more than (2.25k^2)^n permutations of length n. In light of this, we conjecture that no pattern of length k is avoided by more than that many permutations of length n.
0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv
Surprising symmetries in 132-avoiding permutations
We prove that the total number $S_{n,132}(q)$ of copies of the pattern $q$ in all 132-avoiding permutations of length $n$ is the same for $q=231$, $q=312$, or $q=213$. We provide a combinatorial proof for this unexpected threefold symmetry. We then significantly generalize this result to show an exponential number of different pairs of patterns $q$ and $q'$ of length $k$ for which $S_{n,132}(q)=S_{n,132}(q')$ and the equality is non-trivial.
0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv
The Number of Ways to Assemble a Graph
Motivated by the question of how macromolecules assemble, the notion of an {\it assembly tree} of a graph is introduced. Given a graph $G$, the paper is concerned with enumerating the number of assembly trees of $G$, a problem that applies to the macromolecular assembly problem. Explicit formulas or generating functions are provided for the number of assembly trees of several families of graphs, in particular for what we call $(H,ϕ)$-graphs. In some natural special cases, we apply powerful recent results of Zeilberger and Apagodu on multivariate generating functions, and results of Wimp and Zeilberger, to deduce recurrence relations and very precise asymptotic formulas for the number of assembly trees of the complete bipartite graphs $K_{n,n}$ and the complete tripartite graphs $K_{n,n,n}$. Future directions for reseach, as well as open questions, are suggested.
0 citations0 reviewsNo code linkedOpen access