Upper bound on the number of complete maps (Q1364111): Difference between revisions
From MaRDI portal
Created a new Item |
Set profile property. |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Revision as of 04:05, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Upper bound on the number of complete maps |
scientific article |
Statements
Upper bound on the number of complete maps (English)
0 references
8 December 1997
0 references
The study of the asymptotic number of complete maps for the case of permutations begun in [\textit{I. Kovalenko} and \textit{M. Kuper}, An upper bound on the number of complete maps (1995)]. According to [\((*)\) \textit{J. Dénes} and \textit{A. D. Keedwell}, Latin squares and their applications (1974; Zbl 0283.05014)], a complete map of a set \(A\) with the operation \(\circ\) is a bijection \(f: A\to A\) such that the map defined by the formula \(x\to x\circ f(x)\) is also a bijection. If \(A\) is the set of permutations of order \(n\) and \(\circ\) is the operation of addition \(\pmod n\), then no complete maps exist for even \(n\); at the same time, for odd \(n\), the probability that a random permutation is a complete map will be less than \(\exp\{-cn\}\) for sufficiently large \(n\). In \((*)\) it is proved that \(c\geq 0.08854\). The objective of this article is to improve the bound on \(c\), specifically to show that \(c\geq\ln 2/2\approx 0.35\). We also give an enumeration algorithm for all complete maps in a given class with \(2^{(n-1)/2}\) elements. This may increase by the same factor the ``efficiency'' of random search for a complete map.
0 references
number of complete maps
0 references
permutations
0 references
random permutation
0 references
enumeration algorithm
0 references