2025/06/11 by Kolja Knauer, Gil Puig i Surroca · 1 voice
Computer Science · #Advanced Graph Theory Research #Computability, Logic, AI Algorithms #semigroups and automata theory
paper · doi:10.1002/jgt.23262
openalex publication_date 2025/06/11 · openalex created_date 2025/06/12 · openalex updated_date 2026/07/22
ABSTRACT We show that every commutative idempotent monoid (a.k.a. lattice) is the endomorphism monoid of a subcubic graph. This solves a problem of Babai and Pultr and the degree bound is best‐possible. On the other hand, we show that no class excluding a minor can have all commutative idempotent monoids among its endomorphism monoids. As a by‐product, we prove that monoids can be represented by graphs of bounded expansion (reproving a result of Nešetřil and Ossona de Mendez) and ‐cancellative monoids can be represented by graphs of bounded degree. Finally, we show that not all completely regular monoids can be represented by graphs excluding topological minor (strengthening a result of Babai and Pultr).