The paper studies a quantity called PageRank on a specific family of graphs known as Lubotzky-Phillips-Sarnak (LPS) graphs. PageRank, originally the algorithm behind Google Search, assigns importance scores to nodes in a network by simulating a random walker who moves around the graph and occasionally stops at random. LPS graphs are carefully constructed mathematical objects that are nearly as well-connected as theoretically possible, meaning information spreads through them very efficiently. They are also finite but locally look like infinite branching trees, which makes them analytically tractable.
The central question is how much the finite, loopy structure of LPS graphs causes PageRank behavior to differ from what you would see on a perfectly tree-like infinite network. On the infinite tree, there is a classical result describing return probabilities, captured by something called the McKay measure. On the actual finite graphs, cycles (closed loops) allow the random walker to return to its starting point via routes that simply do not exist on a tree. The paper uses a tool called the Ihara zeta function, a kind of generating function that encodes information about all the cycles in the graph, to precisely quantify this extra contribution to return probabilities.
The authors find that when the typical walk length is comparable to the shortest cycle in the graph, cycle-induced corrections become noticeable but are still small. Without assuming anything beyond what is proven in mathematics today, they establish an upper bound on this correction that involves a slowly growing double-logarithmic factor. However, if one assumes the Generalized Riemann Hypothesis, a famous unproven conjecture about the zeros of certain functions from number theory, the correction shrinks to roughly one divided by the total number of vertices in the graph, which is essentially negligible for large graphs. This connects a practical network algorithm to deep unsolved problems in pure mathematics.