On the minimum order of graphs with given semigroup (Q793058): Difference between revisions

Denote by M(n) the smallest positive integer such that for every n- element monoid M there is a graph G with at most M(n) vertices such that End(G) is isomorphic to M. It is proved that \(\sqrt{2}(1+o(1)n\sqrt{\log_ 2n}\leq M(n)\leq n\cdot \sqrt{2n}+O(n).\) The same lower-bound and \(12n \log_ 2n+n\) as an upper bound are given with respect to monoids which are 3-nilpotent (i.e. \(xyz=o\) for a two sided zero element o and for all x,y,\(z\neq 1)\). For k-uniform hypergraphs an upper bound is shown to be 3n for \(k=3,4,..\). and \(n\geq 6k+6.\) Moreover there are given estimates of the number of graphs with n vertices and a given endomorphism monoid.