2018/08/12 by Vsevolod Gubarev, Gubarev, Vsevolod
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Rings and Algebras (math.RA) #math.CO #math.RA
paper · pdf · doi:10.48550/arxiv.1808.03932
118 p. (8 figures, 1 table). It's also a survey on clique-type polynomials. Any comments are welcome!
arxiv created 2018/08/12 · arxiv updated 2018/08/15
We define PC-polynomial of graph which is related to clique, (in)dependence and matching polynomials. The growth rate of partially commutative monoid is equal to the largest root β(G) of PC-polynomial of the corresponding graph. The random algebra is defined in such way that its growth rate equals the largest root of PC-polynomial of random graph. We prove that for almost all graphs all sufficiently large real roots of PC-polynomial lie in neighbourhoods of roots of PC-polynomial of random graph. We show how to calculate the series expansions of the latter roots. The average value of β(G) over all graphs with the same number of vertices is computed. We found the graphs on which the maximal value of β(G) with fixed numbers of vertices and edges is reached. From this, we derive the upper bound of β(G). Modulo one assumption, we do the same for minimal value of β(G). We study the Nordhaus---Gaddum bounds of β(G)+β(G) and β(G)β(G).