On a family of universal cycles for multi-dimensional permutations

Sergey Kitaev; Dun Qiu

doi:10.1016/j.dam.2024.08.010

On a family of universal cycles for multi-dimensional permutations

Sergey Kitaev^*, Dun Qiu

^*Corresponding author for this work

Mathematics And Statistics

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

2 Downloads (Pure)

Abstract

A universal cycle (u-cycle) for permutations of length $n$ is a cyclic word, any size $n$ window of which is order-isomorphic to exactly one permutation of length $n$, and all permutations of length $n$ are covered. It is known that u-cycles for permutations exist, and they have been considered in the literature in several papers from different points of view.

In this paper, we show how to construct a family of u-cycles for multi-dimensional permutations, which is based on applying an appropriate greedy algorithm. Our construction is a generalisation of the greedy way by Gao et al.¥ to construct u-cycles for permutations. We also note the existence of u-cycles for $d$-dimensional matrices.

Original language	English
Pages (from-to)	310-320
Number of pages	11
Journal	Discrete Applied Mathematics
Volume	359
Early online date	24 Aug 2024
DOIs	https://doi.org/10.1016/j.dam.2024.08.010
Publication status	Published - 31 Dec 2024

Funding

The authors are grateful to Glenn Hulbert for sharing with us a copy of [5]. The first author is supported by Leverhulme Research Fellowship, UK (grant reference RF-2023-065\\9). The second author is supported by the National Natural Science Foundation of China (NSFC) grants 12171034 and 12271023.

Keywords

universal cycle
combinatorial generation
greedy algorithm
multi-dimensional permutation
multi-dimensional matrix

Access to Document

10.1016/j.dam.2024.08.010Licence: CC BY 4.0

Kitaev-Qiu-DAM-2024-On-a-family-of-universal-cycles-for-multi-dimensional-permutationsFinal published version, 445 KBLicence: CC BY 4.0

Cite this

@article{db5b42a514a7426e9b1669ca3357f14d,

title = "On a family of universal cycles for multi-dimensional permutations",

abstract = "A universal cycle (u-cycle) for permutations of length \$n\$ is a cyclic word, any size \$n\$ window of which is order-isomorphic to exactly one permutation of length \$n\$, and all permutations of length \$n\$ are covered. It is known that u-cycles for permutations exist, and they have been considered in the literature in several papers from different points of view. In this paper, we show how to construct a family of u-cycles for multi-dimensional permutations, which is based on applying an appropriate greedy algorithm. Our construction is a generalisation of the greedy way by Gao et al.¥ to construct u-cycles for permutations. We also note the existence of u-cycles for \$d\$-dimensional matrices.",

keywords = "universal cycle, combinatorial generation, greedy algorithm, multi-dimensional permutation, multi-dimensional matrix",

author = "Sergey Kitaev and Dun Qiu",

year = "2024",

month = dec,

day = "31",

doi = "10.1016/j.dam.2024.08.010",

language = "English",

volume = "359",

pages = "310--320",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - On a family of universal cycles for multi-dimensional permutations

AU - Kitaev, Sergey

AU - Qiu, Dun

PY - 2024/12/31

Y1 - 2024/12/31

N2 - A universal cycle (u-cycle) for permutations of length $n$ is a cyclic word, any size $n$ window of which is order-isomorphic to exactly one permutation of length $n$, and all permutations of length $n$ are covered. It is known that u-cycles for permutations exist, and they have been considered in the literature in several papers from different points of view. In this paper, we show how to construct a family of u-cycles for multi-dimensional permutations, which is based on applying an appropriate greedy algorithm. Our construction is a generalisation of the greedy way by Gao et al.¥ to construct u-cycles for permutations. We also note the existence of u-cycles for $d$-dimensional matrices.

AB - A universal cycle (u-cycle) for permutations of length $n$ is a cyclic word, any size $n$ window of which is order-isomorphic to exactly one permutation of length $n$, and all permutations of length $n$ are covered. It is known that u-cycles for permutations exist, and they have been considered in the literature in several papers from different points of view. In this paper, we show how to construct a family of u-cycles for multi-dimensional permutations, which is based on applying an appropriate greedy algorithm. Our construction is a generalisation of the greedy way by Gao et al.¥ to construct u-cycles for permutations. We also note the existence of u-cycles for $d$-dimensional matrices.

KW - universal cycle

KW - combinatorial generation

KW - greedy algorithm

KW - multi-dimensional permutation

KW - multi-dimensional matrix

UR - http://arxiv.org/abs/2408.05984

UR - https://www.sciencedirect.com/journal/discrete-applied-mathematics

U2 - 10.1016/j.dam.2024.08.010

DO - 10.1016/j.dam.2024.08.010

M3 - Article

SN - 0166-218X

VL - 359

SP - 310

EP - 320

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

On a family of universal cycles for multi-dimensional permutations

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this