On uniquely k-determined permutations

Sergey Avgustinovich, Sergey Kitaev

Research output: Contribution to journalArticle

6 Citations (Scopus)

Abstract

Motivated by a new point of view to study occurrences of consecutive patterns in permutations, we introduce the notion of uniquely k-determined permutations. 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 the application of the transfer matrix method possible for determining the number of uniquely k-determined permutations.
Original languageEnglish
Pages (from-to)1500-1507
Number of pages8
JournalDiscrete Mathematics
Volume308
Issue number9
Early online date6 Apr 2007
DOIs
Publication statusPublished - May 2008

Fingerprint

Hamiltonians
Transfer matrix method
Permutation
Consecutive
Hamiltonian path
Transfer Matrix Method
Finite Set
Path
Graph in graph theory

Keywords

  • de Bruijn graph
  • consecutive pattern
  • set of prohibitions
  • permutations
  • reconstruction

Cite this

Avgustinovich, Sergey ; Kitaev, Sergey. / On uniquely k-determined permutations. In: Discrete Mathematics. 2008 ; Vol. 308, No. 9. pp. 1500-1507.
@article{d36b7ef76a7d43eab28f9c4600c92604,
title = "On uniquely k-determined permutations",
abstract = "Motivated by a new point of view to study occurrences of consecutive patterns in permutations, we introduce the notion of uniquely k-determined permutations. 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 the application of the transfer matrix method possible for determining the number of uniquely k-determined permutations.",
keywords = "de Bruijn graph, consecutive pattern, set of prohibitions, permutations, reconstruction",
author = "Sergey Avgustinovich and Sergey Kitaev",
year = "2008",
month = "5",
doi = "10.1016/j.disc.2007.03.079",
language = "English",
volume = "308",
pages = "1500--1507",
journal = "Discrete Mathematics",
issn = "0012-365X",
number = "9",

}

On uniquely k-determined permutations. / Avgustinovich, Sergey; Kitaev, Sergey.

In: Discrete Mathematics, Vol. 308, No. 9, 05.2008, p. 1500-1507.

Research output: Contribution to journalArticle

TY - JOUR

T1 - On uniquely k-determined permutations

AU - Avgustinovich, Sergey

AU - Kitaev, Sergey

PY - 2008/5

Y1 - 2008/5

N2 - Motivated by a new point of view to study occurrences of consecutive patterns in permutations, we introduce the notion of uniquely k-determined permutations. 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 the application of the transfer matrix method possible for determining the number of uniquely k-determined permutations.

AB - Motivated by a new point of view to study occurrences of consecutive patterns in permutations, we introduce the notion of uniquely k-determined permutations. 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 the application of the transfer matrix method possible for determining the number of uniquely k-determined permutations.

KW - de Bruijn graph

KW - consecutive pattern

KW - set of prohibitions

KW - permutations

KW - reconstruction

UR - https://personal.cis.strath.ac.uk/sergey.kitaev/index_files/Papers/un-k-determ-perms.pdf

U2 - 10.1016/j.disc.2007.03.079

DO - 10.1016/j.disc.2007.03.079

M3 - Article

VL - 308

SP - 1500

EP - 1507

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 9

ER -