Nilpotent families of endomorphisms of \((\mathcal P(V)^+,\cup)\) (Q1850625)

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.