BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Yuval Roichman appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
We establish upper and lower bounds on the maximal number of steps needed to transform a cyclic permutation to the canonical cyclic permutation using conjugation by adjacent transpositions, and on the diameter of the underlying Schreier graph.
A new descent set statistic on involutions, defined geometrically via their interpretation as matchings, is introduced in this paper, and shown to be equi-distributed with the standard one. This concept is then applied to construct explicit cyclic descent extensions on involutions, standard Young tableaux and Motzkin paths. Schur-positivity of the associated quasisymmetric functions follows.
A character identity which relates irreducible character values of the hyperoctahedral group $B_n$ to those of the symmetric group $S_{2n}$ was recently proved by Lübeck and Prasad. Their proof is algebraic and involves Lie theory. We present a short combinatorial proof of this identity, as well as a generalization to other wreath products.
The ring of cyclic quasi-symmetric functions and its non-Escher subring are introduced in this paper. A natural basis consists of fundamental cyclic quasi-symmetric functions; for the non-Escher subring they arise as toric $P$-partition enumerators, for toric posets $P$ with a total cyclic order. The associated structure constants are determined by cyclic shuffles of permutations. We then prove the following positivity phenomenon: for every non-hook shape $λ$, the coefficients in the expansion of the Schur function $s_λ$ in terms of fundamental cyclic quasi-symmetric functions are nonnegative. The proof relies on the existence of a cyclic descent map on the standard Young tableaux (SYT) of shape $λ$. The theory has applications to the enumeration of cyclic shuffles and SYT by cyclic descents.
For finite reflection groups of types A and B, we determine the diameter of the graph whose vertices are reduced words for the longest element and whose edges are braid relations. This is deduced from a more general theorem that applies to supersolvable hyperplane arrangements.
The problem of finding Schur-positive sets of permutations, originally posed by Gessel and Reutenauer, has seen some recent developments. Schur-positive sets of pattern-avoiding permutations have been found by Sagan et al and a general construction based on geometric operations on grid classes has been given by the authors. In this paper we prove that horizontal rotations of Schur-positive subsets of permutations are always Schur-positive. The proof applies a cyclic action on standard Young tableaux of certain skew shapes and a jeu-de-taquin type straightening algorithm. As a consequence of the proof we obtain a notion of cyclic descent set on these tableaux, which is rotated by the cyclic action on them.
Characterizing sets of permutations whose associated quasisymmetric function is symmetric and Schur-positive is a long-standing problem in algebraic combinatorics. In this paper we present a general method to construct Schur-positive sets and multisets, based on geometric grid classes and the product operation. Our approach produces many new instances of Schur-positive sets, and provides a broad framework that explains the existence of known such sets that until now were sporadic cases.
A short proof to a recent theorem of Giambruno and Mishchenko is given in this note.
The number of $k$-roots of an arbitrary permutation is expressed as an alternating sum of $μ$-unimodal $k$-roots of the identity permutation.
A survey paper, to appear as a chapter in a forthcoming Handbook on Enumeration.
A new family of asymmetric matrices of Walsh-Hadamard type is introduced. We study their properties and, in particular, compute their determinants and discuss their eigenvalues. The invertibility of these matrices implies that certain character formulas are invertible, yielding expressions for the cardinalities of sets of combinatorial objects with prescribed descent sets in terms of character values of the symmetric group.
Arc permutations, which were originally introduced in the study of triangulations and characters, have recently been shown to have interesting combinatorial properties. The first part of this paper continues their study by providing signed enumeration formulas with respect to their descent set and major index. Next, we generalize the notion of arc permutations to the hyperoctahedral group in two different directions. We show that these extensions to type $B$ carry interesting analogues of the properties of type $A$ arc permutations, such as characterizations by pattern avoidance, and elegant unsigned and signed enumeration formulas with respect to the flag-major index.
Arc permutations and unimodal permutations were introduced in the study of triangulations and characters. This paper studies combinatorial properties and structures on these permutations. First, both sets are characterized by pattern avoidance. It is also shown that arc permutations carry a natural affine Weyl group action, and that the number of geodesics between a distinguished pair of antipodes in the associated Schreier graph, as well as the number of maximal chains in the weak order on unimodal permutations, are both equal to twice the number of standard Young tableaux of shifted staircase shape. Finally, a bijection from non-unimodal arc permutations to Young tableaux of certain shapes, which preserves the descent set, is described and applied to deduce a conjectured character formula of Regev.
A weak order on the set of maximal chains of the non-crossing partition lattice is introduced and studied. A $0$-Hecke algebra action is used to compute the radius of the graph on these chains in which two chains are adjacent if they differ in exactly one element.
A permutation representation of a Coxeter group $W$ naturally defines an absolute order. This family of partial orders (which includes the absolute order on $W$) is introduced and studied in this paper. Conditions under which the associated rank generating polynomial divides the rank generating polynomial of the absolute order on $W$ are investigated when $W$ is finite. Several examples, including a symmetric group action on perfect matchings, are discussed. As an application, a well-behaved absolute order on the alternating subgroup of $W$ is defined.
A generating set for the wreath product $\ZZ_r \wr S_n$ which leads to a nicely behaved weak order is presented, and properties of the resulting order are studied.
Flips of diagonals in colored triangle-free triangulations of a convex polygon are interpreted as moves between two adjacent chambers in a certain graphic hyperplane arrangement. Properties of geodesics in the associated flip graph are deduced. In particular, it is shown that: (1) every diagonal is flipped exactly once in a geodesic between distinguished pairs of antipodes; (2) the number of geodesics between these antipodes is equal to twice the number of Young tableaux of a truncated shifted staircase shape.
Unexpected product formulas for the number of standard Young tableaux of certain truncated shapes are found and proved. These include shifted staircase shapes minus a square in the NE corner, rectangular shapes minus a square in the NE corner, and some variations.