Posets of finite functions
type: Item
instance of: scholarly article
title: Posets of finite functions
zbMATH Open document ID: 1352.06002
author: Konrad Pióro
published in: The Electronic Journal of Combinatorics
publication date: 2016-01-25T00:00:00Z
full work available at URL: v23i1p3
review text: Summary: The symmetric group \(S(n)\) is partially ordered by Bruhat order. This order is extended by \textit{L. E. Renner} [Linear algebraic monoids. Berlin: Springer (2005; Zbl 1085.20041)] to the set of partial injective functions of \( \{ 1, 2, \ldots, n \} \). This poset is investigated by \textit{M. Fortin} in [Electron. J. Comb. 15, No. 1, Research Paper R62, 30 p. (2008; Zbl 1192.06004)]. In this paper we show that Renner order can be also defined for sets of all functions, partial functions, injective and partial injective functions from \( \{ 1, 2, \ldots, n \} \) to \( \{ 1, 2, \ldots, m \} \). Next, we generalize Fortin's results on these posets, and also, using simple facts and methods of linear algebra, we give simpler and shorter proofs of some fundamental Fortin's results. We first show that these four posets can be order embedded in the set of \( n \times m \)-matrices with non-negative integer entries and with the natural componentwise order. Second, matrix representations of the Dedekind-MacNeille completions of our posets are given. Third, we find join- and meet-irreducible elements for every finite sublattice of the lattice of all \( n \times m \)-matrices with integer entries. In particular, we obtain join- and meet-irreducible elements of these Dedekind-MacNeille completions. Hence and by general results concerning Dedekind-MacNeille completions, join- and meet-irreducible elements of our four posets of functions are also found. Moreover, subposets induced by these irreducible elements are precisely described.
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 06B23
zbMATH DE Number: 6534986
zbMATH Keywords: finite functions
zbMATH Keywords: partial functions
zbMATH Keywords: partial injective functions
zbMATH Keywords: matrix representation of function
zbMATH Keywords: Bruhat order
zbMATH Keywords: Renner order
zbMATH Keywords: posets of functions
zbMATH Keywords: posets of matrices
zbMATH Keywords: join-irreducible element
zbMATH Keywords: meet-irreducible element
zbMATH Keywords: Dedekind-MacNeille completion
MaRDI profile type: Publication
cites work: Combinatorics of Coxeter Groups
cites work: Q4705310
cites work: Q3934450
cites work: Q3956998
cites work: Q4530231
cites work: The MacNeille completion of the poset of partial injective functions
cites work: Bases for the Bruhat-Chevalley order on all finite Coxeter groups
cites work: Lattices and bases of Coxeter groups
cites work: Order dimension, strong Bruhat order and lattice properties for posets
cites work: Linear algebraic monoids.
cites work: Q3225387
description: scientific article; zbMATH DE number 6534986