On uniquely k-determined permutations

DOI10.1016/J.DISC.2007.03.079zbMATH Open1134.05002arXivmath/0610333OpenAlexW2092545680MaRDI QIDQ2477375FDOQ2477375

Authors: Sergey Kitaev, Sergey Avgustinovich 

Publication date: 13 March 2008

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: There are several approaches to study occurrences of consecutive patterns in permutations such as the inclusion-exclusion method, the tree representations of permutations, the spectral approach and others. We propose yet another approach to study occurrences of consecutive patterns in permutations. The approach is based on considering the graph of patterns overlaps, which is a certain subgraph of the de Bruijn graph. While applying our approach, the notion of a uniquely $k$-determined permutation appears. We give two criteria for a permutation to be uniquely $k$-determined: one in terms of the distance between two consecutive elements in a permutation, and the other one in terms of directed hamiltonian paths in the certain graphs called path-schemes. Moreover, we describe a finite set of prohibitions that gives the set of uniquely $k$-determined permutations. Those prohibitions make applying the transfer matrix method possible for determining the number of uniquely $k$-determined permutations.

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

Recommendations

• ON THE NUMBER OFA-PERMUTATIONS
• Permutations Fixing ak-set
• Uniquely sorted permutations
• On \(k\)-neighbor separated permutations
• On the enumeration of permutominoes
• On permutations of \(\{1,\ldots ,n\}\) and related topics
• On the combinatorics of permutations
• On a question of the Kourovka notebook concerning permutability

zbMATH Keywords

permutationreconstructionde Bruijn graphconsecutive patternset of prohibitions

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Directed graphs (digraphs), tournaments (05C20) Eulerian and Hamiltonian graphs (05C45)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Universal cycles for combinatorial structures
• Consecutive patterns in permutations
• Partially ordered generalized patterns
• A spectral approach to consecutive pattern-avoiding permutations
• On Unavoidable Sets of Word Patterns
• Colouring prime distance graphs
• Multi-avoidance of generalised patterns
• Crucial words and the complexity of some extremal problems for sets of prohibited words
• Systematic generation of ordered sequences using recurrence relations
• Independent sets on path-schemes

Cited In (12)

• Permutations Fixing ak-set
• Atomicity and Well Quasi-Order for Consecutive Orderings on Words and Permutations
• The match of a random permutation has the FKG property
• The solution to the partition reconstruction problem
• The joint distribution of consecutive patterns and descents in permutations avoiding 3-1-2
• Cycles in the graph of overlapping permutations avoiding barred patterns
• Permutations with exactly one copy of a monotone pattern of length \(k\), and a generalization
• Number of cycles in the graph of 312-avoiding permutations
• Enumerating anchored permutations with bounded gaps
• Enumerating cycles in the graph of overlapping permutations
• K-permutivity
• Counting crucial permutations with respect to monotone patterns

Uses Software

• OEIS

This page was built for publication: On uniquely \(k\)-determined permutations

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