Imagine you have a network of nodes connected by edges, and at each step you randomly pick an edge and replace the values at both endpoints with their average. This is called the "repeated averages process," and a natural question is: how long does it take for all the values across the network to become roughly equal? This convergence time is called the mixing time. Researchers have worked out the mixing time for many specific types of networks, but no clean general formula has been found that works for all connected networks.
A conjecture had been proposed suggesting that the mixing time should follow a specific formula involving the number of edges, the logarithm of the number of nodes, and a quantity called the spectral gap (which measures how well-connected a graph is). The authors disprove this conjecture by constructing a specific family of counterexample graphs, each built by taking a complete graph (where every node is connected to every other node) and attaching a single extra node connected to just one node of the clique, like a pendant leaf hanging off a dense core.
For this family of graphs, the spectral gap turns out to equal 1, and the mixing time grows like the square of the number of nodes, with no logarithmic correction factor. The conjecture would have predicted a logarithmic factor that simply is not there. The key geometric reason this happens is that the so-called Fiedler eigenvector (the eigenvector associated with the spectral gap) is highly concentrated on the single leaf node rather than being spread across the graph. This localization causes the standard formula to overestimate the mixing time, showing that the spectral gap alone, combined with the edge count and a log factor, is not sufficient to capture mixing behavior in general networks.