Enumeration of order preserving maps

DOI10.1007/BF00419036MaRDI QIDQ1205152zbMATH OpenFDO

Authors Dwight Duffus, Vojtěch Rödl, Bill Sands, R. E. Woodrow

Publication date 1 April 1993

Published in Order (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF00419036

zbMATH Keywords

crownsexponential characterfencesmartingalenumbers of endomorphismsorder-preserving mapsstochastic process

Mathematics Subject Classification ID

Asymptotic enumeration (05A16) Combinatorics of partially ordered sets (06A07)

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.

Recommendations

• The number of order-preserving maps of fences and crowns
• On the endomorphism semigroup of an ordered set
• The number of order-preserving maps between fences and crowns
• Endomorphisms of the semigroup of order-preserving mappings.
• Endomorphisms of Partially Ordered Sets

Cites work

• Automorphisms, isotone self-maps and cycle-free orders
• scientific article; zbMATH DE number 4152425 (Why is no real title available?)
• scientific article; zbMATH DE number 736303 (Why is no real title available?)
• scientific article; zbMATH DE number 3245483 (Why is no real title available?)
• Note on a “Square” Functional Equation
• Probability Inequalities for Sums of Bounded Random Variables
• The number of order-preserving maps of fences and crowns

Cited in

(16)

• The number of order-preserving maps of fences and crowns
• Boolean layer cakes
• Algorithms for the fixed point property
• Counting the number of isotone selfmappings of crowns
• Automorphisms and isotone self-maps of ordered sets with top and bottom
• The formula for the number of order-preserving selfmappings of a fence
• Automorphisms, isotone self-maps and cycle-free orders
• The number of order-preserving maps between fences and crowns
• The endomorphism spectrum of an ordered set
• The automorphism conjecture for ordered sets of dimension 2 and interval orders
• The automorphism conjecture for small sets and series parallel sets
• scientific article; zbMATH DE number 3841924 (Why is no real title available?)
• Set mappings of unrestricted order
• Endomorphisms of Partially Ordered Sets
• scientific article; zbMATH DE number 1419646 (Why is no real title available?)
• Counting and Computing Join-Endomorphisms in Lattices

This page was built for publication: Enumeration of order preserving maps

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