** "Geometry and Analysis on Groups" Research Seminar **

**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\).
- 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 on \(\beta(G): \beta(G) < n - (0.941k)/n\)
for \(n\gg1\).
Thus, we obtain new versions of Lovász local lemma.
- We investigate the analogues of Nordhaus-Gaddum inequalities for \(\beta(G)\).
- Applying random graphs, we prove that the average value of
\(\beta(G)\) on graphs with \(n\gg 1\) vertices
asymptotically equals (approx) \(0.672n\).