Graphs with edge-preserving majority functions (Q1196742)

A subgraph \(H\) of a graph \(G\) is said to be a retract of \(G\) if there is a graph homomorphism (i.e., an edge-preserving map) \(r:G\to H\) whose composition with the insertion \(H\to G\) is the identity map on \(H\). Any retract \(H\subseteq G\) is an isometric subgraph of \(G\). In the paper, a bipartite graph is said to be an absolute retract if it is a retract of every bipartite graph in which it isometrically embeds. The main result of the paper states that a bipartite graph is an absolute retract if and only if there exists a homomorphism \(m:G\times G\times G\to G\) satisfying the ``majority condition'' \(m(u,u,v)=m(u,v,u)=m(v,u,u)=u\) for any \(u,v\in V(G)\); here \(G\times G\times G\) denotes the direct (also known as the relational) product of three copies of \(G\). Similar relationship between absolute retracts and majority morphisms is known from ordered set theory or topology (see, e.g., \textit{J. van Mill} and \textit{M. van de Vel} [Topology, Proc. Conf. Ohio Univ. 1979, Vol. 4, No. 1, 193-200 (1980; Zbl 0462.54024)]).