Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEquivalence Classes of Permutations under Various Relations Generated by Constrained Transpositions
116
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We consider a large family of equivalence relations on permutations in Sn that generalise those discovered by Knuth in his study of the Robinson-Schensted correspondence. In our most general setting, two permutations are equivalent if one can be obtained from the other by a sequence of pattern-replacing moves of prescribed form; however, we limit our focus to patterns where two elements are transposed, subject to the constraint that a third element of a suitable type be in a suitable position. For various instances of the problem, we compute the number of equivalence classes, determine how many n-permutations are equivalent to the identity permutation, or characterise this equivalence class. Although our results feature familiar integer sequences (e.g., Catalan, Fibonacci, and Tribonacci numbers) and special classes of permutations (layered, connected, and 123-avoiding), some of the sequences that arise appear to be new.
rate research
Read More
In this paper, we compute and demonstrate the equivalence of the joint distribution of the first letter and descent statistics on six avoidance classes of permutations corresponding to two patterns of length four. This distribution is in turn shown to be equivalent to the distribution on a restricted class of inversion sequences for the statistics that record the last letter and number of distinct positive letters, affirming a recent conjecture of Lin and Kim. Members of each avoidance class of permutations and also of the class of inversion sequences are enumerated by the $n$-th large Schroder number and thus one obtains a new bivariate refinement of these numbers as a consequence. We make use of auxiliary combinatorial statistics, special generating functions (specific to each class) and the kernel method to establish our results. In some cases, we utilize the conjecture itself in a creative way to aid in solving the system of functional equations satisfied by the associated generating functions.
The independence polynomial of a graph is the generating polynomial for the number of independent sets of each size. Two graphs are said to be textit{independence equivalent} if they have equivalent independence polynomials. We extend previous work by showing that independence equivalence class of every odd path has size 1, while the class can contain arbitrarily many graphs for even paths. We also prove that the independence equivalence class of every even cycle consists of two graphs when $nge 2$ except the independence equivalence class of $C_6$ which consists of three graphs. The odd case remains open, although, using irreducibility results from algebra, we were able show that for a prime $p geq 5$ and $nge 1$ the independence equivalence class of $C_{p^n}$ consists of only two graphs.
A system $mathcal M$ of equivalence relations on a set $E$ is emph{semirigid} if only the identity and constant functions preserve all members of $mathcal M$. We construct semirigid systems of three equivalence relations. Our construction leads to the examples given by Zadori in 1983 and to many others and also extends to some infinite cardinalities. As a consequence, we show that on every set of at most continuum cardinality distinct from $2$ and $4$ there exists a semirigid system of three equivalence relations.
We extend some recent results about bounded invariant equivalence relations and invariant subgroups of definable groups: we show that type-definability and smoothness are equivalent conditions in a wider class of relations than heretofore considered, which includes all the cases for which the equivalence was proved before. As a by-product, we show some analogous results in purely topological context (without direct use of model theory).
This note studies the existence of quotients by finite set theoretic equivalence relations. May 18: Substantial revisions with a new appendix by C. Raicu
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
