Enumeration of order preserving maps
type: Item
instance of: scholarly article
title: Enumeration of order preserving maps
zbMATH Open document ID: 0766.06005
DOI: 10.1007/BF00419036
author: Dwight Duffus
author: Vojtěch Rödl
author: Bill Sands
author: R. E. Woodrow
published in: Order
publication date: 1993-04-01T00:00:00Z
review text: If \(X\) is an ordered set, then \(\text{End}(X)\) denotes the set of all endomorphisms of \(X\) (i.e. order-preserving maps of \(X\) to \(X\)). Let \(e(X)=|\text{End}(X)|\). For a fixed positive integer \(n\), let \(e_ n=\min(e(X); | X|=n)\). The authors prove that for \(n\geq 3\), \(e_ n\geq (2^{2/3})^ n\) (and in the case of length one, there are at least \(2^ n\) endomorphisms). Furthermore, asymptotic estimates for the numbers of endomorphisms of crowns and fences are given. The exponential character of an infinite class of finite ordered sets is defined, and it is computed for several classes of ordered sets inspired by crowns and fences. The authors use interesting (among others, probabilistic) methods.
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 05A16
zbMATH DE Number: 146913
zbMATH Keywords: stochastic process
zbMATH Keywords: martingale
zbMATH Keywords: order-preserving maps
zbMATH Keywords: numbers of endomorphisms
zbMATH Keywords: crowns
zbMATH Keywords: fences
zbMATH Keywords: exponential character
reviewed by: Jiří Rachůnek
MaRDI profile type: Publication
cites work: Q5532570
cites work: The number of order-preserving maps of fences and crowns
cites work: Probability Inequalities for Sums of Bounded Random Variables
cites work: Automorphisms, isotone self-maps and cycle-free orders
cites work: Q4326647
cites work: Q3481743
cites work: Note on a “Square” Functional Equation
description: scientific article; zbMATH DE number 146913