Number of cycles in the graph of 312-avoiding permutations

DOI10.1016/J.JCTA.2014.09.004MaRDI QIDQ472163zbMATH OpenOpenAlexFDO

Authors Richard Ehrenborg, Sergey Kitaev, Einar Steingrímsson

Publication date 19 November 2014

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.1520

zbMATH Keywords

cyclespattern-avoiding permutationsgraph of overlapping permutations

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Directed graphs (digraphs), tournaments (05C20) Enumeration in graph theory (05C30) Paths and cycles (05C38)

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 $pi=p{i}_{1}p{i}_2\mathrm{...}p{i}_{n+1}$ there is a directed edge from the standardization of $p{i}_{1}p{i}_2\mathrm{...}p{i}_n$ to the standardization of $p{i}_{2}p{i}_3\mathrm{...}p{i}_{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.

Recommendations

• Number of cycles in the graph of 312-avoiding permutations
• Cycles in the graph of overlapping permutations avoiding barred patterns
• Enumerating cycles in the graph of overlapping permutations
• An upper bound on the number of \((132, 213)\)-avoiding cyclic permutations
• Pattern-restricted permutations composed of 3-cycles

Cites work

• scientific article; zbMATH DE number 3422259 (Why is no real title available?)
• scientific article; zbMATH DE number 3068971 (Why is no real title available?)
• A dynamical property unique to the Lucas sequence
• A spectral approach to consecutive pattern-avoiding permutations
• Affine permutations of type \(A\)
• Arithmetic and growth of periodic orbits
• Classification of bijections between 321- and 132-avoiding permutations
• Enumerating pattern avoidance for affine permutations
• Juggling and applications to \(q\)-analogues
• On uniquely k-determined permutations
• Patterns in permutations and words.
• Universal cycles for combinatorial structures

Cited in

(6)

• Some statistics on the hypercubes of Catalan permutations
• An upper bound on the number of \((132, 213)\)-avoiding cyclic permutations
• Generalizing the classic greedy and necklace constructions of de Bruijn sequences and universal cycles
• Cycles in the graph of overlapping permutations avoiding barred patterns
• Number of cycles in the graph of 312-avoiding permutations
• Enumerating cycles in the graph of overlapping permutations

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Number of cycles in the graph of 312-avoiding permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q472163)