Number of cycles in the graph of 312-avoiding permutations

Richard Ehrenborg; Sergey Kitaev; Einar Steingrimsson

doi:10.1016/j.jcta.2014.09.004

Number of cycles in the graph of 312-avoiding permutations

Richard Ehrenborg, Sergey Kitaev, Einar Steingrimsson

Research output: Contribution to journal › Article › peer-review

3 Citations (Scopus)

132 Downloads (Pure)

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.

Original language	English
Pages (from-to)	1-18
Number of pages	18
Journal	Journal of Combinatorial Theory Series A
Volume	129
Early online date	1 Oct 2014
DOIs	https://doi.org/10.1016/j.jcta.2014.09.004
Publication status	Published - Jan 2015

Keywords

pattern avoiding permutations
graph of overlapping permutations
cycles

Access to Document

10.1016/j.jcta.2014.09.004

Ehrenborg-etal-JCTSA2015-number-of-cycles-in-the-graph-of-312-avoiding-permutationsAccepted author manuscript, 368 KBLicence: CC BY-NC-ND 4.0

Cite this

@article{27e2446dda9148289be52001dfe83533,

title = "Number of cycles in the graph of 312-avoiding permutations",

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.",

keywords = "pattern avoiding permutations, graph of overlapping permutations, cycles",

author = "Richard Ehrenborg and Sergey Kitaev and Einar Steingrimsson",

year = "2015",

month = jan,

doi = "10.1016/j.jcta.2014.09.004",

language = "English",

volume = "129",

pages = "1--18",

journal = "Journal of Combinatorial Theory Series A ",

issn = "0097-3165",

}

TY - JOUR

T1 - Number of cycles in the graph of 312-avoiding permutations

AU - Ehrenborg, Richard

AU - Kitaev, Sergey

AU - Steingrimsson, Einar

PY - 2015/1

Y1 - 2015/1

N2 - 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.

AB - 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.

KW - pattern avoiding permutations

KW - graph of overlapping permutations

KW - cycles

UR - http://arxiv.org/abs/1310.1520

UR - http://www.sciencedirect.com/science/journal/00973165

U2 - 10.1016/j.jcta.2014.09.004

DO - 10.1016/j.jcta.2014.09.004

M3 - Article

SN - 0097-3165

VL - 129

SP - 1

EP - 18

JO - Journal of Combinatorial Theory Series A

JF - Journal of Combinatorial Theory Series A

ER -

Number of cycles in the graph of 312-avoiding permutations

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this