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

Producción científica: Article › revisión exhaustiva

3 Citas (Scopus)

Resumen

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.

Idioma original	English
Páginas (desde-hasta)	1-18
Número de páginas	18
Publicación	Journal of Combinatorial Theory. Series A
Volumen	129
DOI	https://doi.org/10.1016/j.jcta.2014.09.004
Estado	Published - ene 2015

Nota bibliográfica

Publisher Copyright:
© 2014 Elsevier Inc.

Financiación

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 .

Financiadores	Número del financiador
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

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Acceder al documento

10.1016/j.jcta.2014.09.004

Otros archivos y enlaces

Citar esto

@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

Resumen

Nota bibliográfica

Financiación

ASJC Scopus subject areas

Acceder al documento

Otros archivos y enlaces

Huella

Citar esto