论文标题
关于稀疏图类的内态普遍性
On endomorphism universality of sparse graph classes
论文作者
论文摘要
我们表明，每个交换性的单型基（又称晶格）都是亚基图的内态性。这解决了Babai和Pultr的问题[J.梳子〜理论，ser。另一方面，我们表明，没有一个不包括未成年人的阶级可以在其内态单体中都具有所有交换性的单身性。作为副产品，我们证明可以通过有界膨胀的图（依靠nešetùilil和Ossona de Mendez的结果）来表示单体，并且可以通过有限程度的图表示。最后，我们表明，并非所有完全规则的单体都可以通过不包括拓扑小调（增强Babai和Pultr的结果）来表示。
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).
