Number of cycles in the graph of 312-avoiding permutations

Ehrenborg, Richard and Kitaev, Sergey and Steingrimsson, Einar (2015) Number of cycles in the graph of 312-avoiding permutations. Journal of Combinatorial Theory Series A, 129. pp. 1-18. ISSN 0097-3165 (https://doi.org/10.1016/j.jcta.2014.09.004)

[thumbnail of Ehrenborg-etal-JCTSA2015-number-of-cycles-in-the-graph-of-312-avoiding-permutations]
Preview
 Text. Filename: Ehrenborg_etal_JCTSA2015_number_of_cycles_in_the_graph_of_312_avoiding_permutations.pdf
Accepted Author Manuscript
License: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 logo
Download (377kB)| Preview

Abstract

The graph of overlapping permutations is defined in a way analogous to the De Bruijn graph on strings of symbols. That is, for every permutation π=π1π2...πn+1 there is a directed edge from the standardization of π1π2...πn to the standardization of π2π3...πn+1. We give a formula for the number of cycles of length d in the subgraph of overlapping 312-avoiding permutations. Using this we also give a refinement of the enumeration of 312-avoiding affine permutations and point out some open problems on this graph, which so far has been little studied.

CORE (COnnecting REpositories)