Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2209.15453 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
Table des matières:
- 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 [J. Comb.~Theory, Ser.~B, 1980] 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 $k$-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).