Time: 2018.03.20, 15:15–17:00
Location: Seminarraum 9, Oskar-Morgenstern-Platz 1, 2.Stock
Title: "The growth rate of partially commutative monoids and algebras."
Speaker: Vsevolod Gubarev (Universität Wien)
Abstract: Given a simple finite graph $$G(V,E)$$, we are interested to know how much different words of the length $$t$$ will be in the alphabet $$V$$ if, given a word, we can interchange neighbor letters provided they are connected in $$G$$. Denote the answer as $$m(t)$$. More precisely, we are interested on the growth rate $$\beta(G)$$ of the sequence $$\{m(t)\}$$. It is known that the $$\beta(G)$$ equals the largest root of some special polynomial with integer coefficients depending on the numbers of cliques in $$G$$.
1. We find a graph on which $$\beta(G)$$ reaches the largest value if the numbers $$n = |V|$$ and $$k = |E|$$ are fixed.
2. We find the upper bound on $$\beta(G): \beta(G) < n - (0.941k)/n$$ for $$n\gg1$$. Thus, we obtain new versions of Lovász local lemma.
3. We investigate the analogues of Nordhaus-Gaddum inequalities for $$\beta(G)$$.
4. Applying random graphs, we prove that the average value of $$\beta(G)$$ on graphs with $$n\gg 1$$ vertices asymptotically equals (approx) $$0.672n$$.