The paper studies a combinatorial question about graphs: given a graph with n vertices, how few pairs of vertices can have "similar" degrees? Here, two vertices count as having similar degrees if the difference between their degrees is less than some threshold k. The authors want to find the minimum possible number of such similar pairs, which they call f(n,k), over all possible graphs on n vertices.
The motivation comes from probability theory. A related version of this problem, but for bipartite graphs, was recently used by Cichomski and Petrov to prove the Burdzy-Pitman conjecture, which concerns how spread out the sum of independent, identically distributed random variables can be. Essentially, graph-theoretic extremal problems about degree distributions turn out to encode useful information about probability distributions, creating a surprising bridge between combinatorics and probability.
The paper works out the answer to this minimization problem for ordinary (non-bipartite) graphs. The authors determine exactly how few vertex pairs must have degrees within k of each other, no matter how cleverly the graph is constructed. This kind of result belongs to a broader area of combinatorics called extremal graph theory, where the goal is to find graphs that push some quantity to its extreme value. Beyond its connection to probability, the result is also of independent interest as a clean structural question about how unevenly degrees can be distributed across the vertices of a graph.