Talk information

Date: Sunday, August 4, 2024
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Shlomo Hoory (Tel Hai College)
Title: On the growth rate of the universal covering tree


Abstract:

This work studies the relation between two graph parameters, $\rho$ and $\Lambda$. For an undirected graph $G$, $\rho(G)$ is the growth rate of its universal cover, while $\Lambda(G)$ is the weighted geometric average of the vertex degree minus one, where the vertex weights are proportional to the degree.
It is well known that $\rho(G) \geq \Lambda(G)$. Graphs satisfying the equality, $\rho(G)=\Lambda(G)$, are those for which the following statements are true:

  1. For a random lift of $G$, the mixing time of the non-backtracking random walk (NBRW) is the same as its diameter up to $(1+o(1))$ factor with high probability.

  2. The Moore bound for lifts of $G$ is the same as the Moore bound for graphs which have the same degree distribution as $G$, where the Moore bound is the best known lower bound on the size of a girth $g$ graph, for a given graph family.

This work derives a necessary and sufficient condition for the equality to hold. A non-backtracking path $P$ in $G$ is called a suspended path if all its internal vertices have degree two, while its endpoints have larger degree. We prove that $\rho(G) = \Lambda(G)$ iff every suspended path $P$ in $G$ satisfies the equality $(\deg(v)-1)(\deg(u)-1) = \Lambda(G)^{2l}$, where $u$ and $v$ are the endpoints of $P$ and $l$ is its length.

Graphs with $\rho = \Lambda$ include regular graphs and bipartite-biregular graphs, possibly with replacement of all edges by a length $k$ path. As a consequence of our result, we give an infinite family of graphs with $\rho = \Lambda$ that are not in the above list.

This is joint work with Idan Eisner, Tel-Hai College