"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\).
  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\).