Number of cycles in the graph of 312-avoiding permutations

Richard Ehrenborg; Sergey Kitaev; Einar Steingrímsson

doi:10.1016/j.jcta.2014.09.004

Number of cycles in the graph of 312-avoiding permutations

Richard Ehrenborg
, Sergey Kitaev
, Einar Steingrímsson

Mathematics

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

3 Scopus citations

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 π=π₁π₂⋯π_n+1 there is a directed edge from the standardization of π₁π₂⋯π_n to the standardization of π₂π₃⋯π_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
DOIs	https://doi.org/10.1016/j.jcta.2014.09.004
State	Published - Jan 2015

Bibliographical note

Publisher Copyright:
© 2014 Elsevier Inc.

Funding

The authors thank the two referees for their helpful comments. The first author was partially supported by National Science Foundation grant DMS 0902063 and National Security Agency grant H98230-13-1-0280 . The last author was supported by grant No. 090038013 from the Icelandic Research Fund .

Funders	Funder number
Icelandic Centre for Research
U.S. Department of Energy Chinese Academy of Sciences Guangzhou Municipal Science and Technology Project Oak Ridge National Laboratory Extreme Science and Engineering Discovery Environment National Science Foundation National Energy Research Scientific Computing Center National Natural Science Foundation of China	0902063
National Security Agency	090038013, H98230-13-1-0280

Keywords

Cycles
Graph of overlapping permutations
Pattern avoiding permutations

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1016/j.jcta.2014.09.004

Cite this

@article{32b65a49a3b64b909238a57ba0fa0c56,

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 = "Cycles, Graph of overlapping permutations, Pattern avoiding permutations",

author = "Richard Ehrenborg and Sergey Kitaev and Einar Steingr{\'i}msson",

note = "Publisher Copyright: {\textcopyright} 2014 Elsevier Inc.",

year = "2015",

month = jan,

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

language = "English",

volume = "129",

pages = "1--18",

}

TY - JOUR

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

AU - Ehrenborg, Richard

AU - Kitaev, Sergey

AU - Steingrímsson, 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 - Cycles

KW - Graph of overlapping permutations

KW - Pattern avoiding permutations

UR - https://www.scopus.com/pages/publications/84907697231

UR - https://www.scopus.com/pages/publications/84907697231#tab=citedBy

U2 - 10.1016/j.jcta.2014.09.004

DO - 10.1016/j.jcta.2014.09.004

M3 - Article

AN - SCOPUS:84907697231

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

Bibliographical note

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this