Vsevolod Gubarev (Novoszibirszk-Vienna): PC-polynomial on graph

Given a graph $G$, we are interested on the properties of $\beta(G)$, the largest root of PC-polynomial, a polynomial with integer coefficients depending on the numbers of cliques in $G$ (almost the same as clique or (in)dependence polynomial). Applying the result of P. Csikvári, we find a graph on which $\beta(G)$ reaches the largest value if the numbers $n = |V|$ and $k = |E|$ are fixed. We find the upper bound $\beta(G) < n - (0.941k)/n$ for $n>>1$ which is useful to get new versions of Lovász local lemma. We investigate the analogues of Nordhaus-Gaddum inequalities for $\beta(G)$. Considering random graphs, the average value of $\beta(G)$ on graphs with $n$ vertices asymptotically equals ≈0.672n.