Nilpotent families of endomorphisms of \((\mathcal P(V)^+,\cup)\)
type: Item
instance of: scholarly article
title: Nilpotent families of endomorphisms of \((\mathcal P(V)^+,\cup)\)
zbMATH Open document ID: 1019.05029
author: Dmitry G. Fon-Der-Flaass
author: J. Nešetřil
author: Alexandr Kostochka
author: André Raspaud
author: Éric Sopena
published in: Journal of Combinatorial Theory. Series B
publication date: 2002-12-10T00:00:00Z
review text: Let \(V\) be a finite set, \(|V|=n.\) Denote by \({\mathcal P}(V)^+\) the set of all non-empty subsets of \(V\). Consider endomorphisms of the semi-lattice \(({\mathcal P}(V)^+,\cup)\), that is, mappings \(\varphi:{\mathcal P}(V)^+\to {\mathcal P}(V)^+\) such that \(\varphi(X\cup Y)=\varphi(X)\cup \varphi(Y).\) A directed graph \(G=(V,A)\) is \(k\)-nice if for all \(u,v\in V,\) and for all orientations of the edges of an undirected path of length \(k\), there exists a \(u\)-\(v\) walk of length \(k\) in \(G\) whose orientation coincides with that of the given path. A graph is nice if it is \(k\)-nice for some \(k.\) In the paper ``niceness'' of graphs as a special case of a more general and natural notion of nilpotency of semigroups of endomorphisms of \(({\mathcal P}(V)^+,\cup)\) is studied. It is shown that the nilpotency class can be exponentially large if the number of generators is \(n\). The main result is a polynomial in \(n\) upper bound on the nilpotency class when the generators have a special form. \textit{P. Hell, A. V. Kostochka, A. Raspaud}, and \textit{E. Sopena} [Discrete Math. 234, 39-51 (2001; Zbl 0990.05058)] found characterizations of non-nice graphs in terms of the so-called ``black holes''. In the paper under review it is proven that in general the simplest black holes can be more complicated than in previously considered cases.
Mathematics Subject Classification ID: 05C25
zbMATH DE Number: 1843845
zbMATH Keywords: \(k\)-nice graph
zbMATH Keywords: semigroup of endomorphisms
reviewed by: U. A. Rozikov
MaRDI profile type: Publication
full work available at URL: jctb.2002.2116
OpenAlex ID: W2044455066
cites work: On universal graphs for planar oriented graphs of a given girth
cites work: On the maximum average degree and the oriented chromatic number of a graph
cites work: On nice graphs
cites work: On Powers of Non-Negative Matrices
cites work: Colorings and girth of oriented planar graphs
cites work: Unzerlegbare, nicht negative Matrizen
DOI: 10.1006/JCTB.2002.2116
Recommended article: Q3123837
Recommended article: Q5664119
Recommended article: Structure of endomorphism semigroup of endomappings of some particular rooted trees
Recommended article: On concrete characterization problem of endomorphism semigroups of graphs
Recommended article: Q3831034
Recommended article: Endomorphism semigroups of 2-nilpotent binary relations.
Recommended article: Q4982506
Recommended article: The non-nilpotent graph of a semigroup.
Recommended article: Q5150639
Recommended article: Q3729177
description: scientific article; zbMATH DE number 1843845