On the minimum order of graphs with given semigroup
type: Item
instance of: scholarly article
title: On the minimum order of graphs with given semigroup
zbMATH Open document ID: 0538.05054
DOI: 10.1016/0095-8956(84)90021-2
author: Václav Koubek
author: Vojtěch Rödl
published in: Journal of Combinatorial Theory. Series B
publication date: 1984-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 20M30
zbMATH DE Number: 3855163
zbMATH Keywords: uniform hypergraphs
zbMATH Keywords: endomorphism monoid
reviewed by: Ulrich Knauer
MaRDI profile type: Publication
full work available at URL: 0095-8956(84)90021-2
OpenAlex ID: W2034331627
cites work: On the Minimum Order of Graphs with Given Group
cites work: Infinite digraphs with given regular automorphism groups
cites work: On Lovász' lattice reduction and the nearest lattice point problem
cites work: Subdirect unions in universal algebra
cites work: A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
cites work: Some remarks on the theory of graphs
cites work: Asymmetric graphs
cites work: Q4065548
cites work: Q5572358
cites work: Relations (graphs) with given finitely generated semigroups
cites work: Graphs and k-Societies
cites work: The Number of Semigroups of Order n
cites work: Q3880849
cites work: Q3208855
description: scientific article; zbMATH DE number 3855163