{"id":"arxiv/2608.27537","url":"https://arxiv.org/abs/2608.27537","tags":["math.CO"],"score":0,"title":"Maximum spread of vertex degrees in a simple graph","domain":"math.CO","source":"arxiv","authors":["Sergey Onishchenko"],"reviews":0,"subject":"math.CO","summary":"We consider the following problem: let $n>k$ --- positive integers, $G$ --- a graph on $n$ vertices (undirected, without loops or multiple edges). Let $h_k(G)$ denote the number of unordered pairs of vertices of the graph $G$ whose degrees differ by less than $k$. We seek to determine the smallest possible value $f(n,k)$ of $h_k(G)$. The interest in this question is motivated by the fact that the bipartite analogue of the problem allowed S. Cichomski and F. Petrov \\cite{CP} to prove the Burdzy--Pitman conjecture on the spread of independent identically distributed random variables.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-27","reactions":{}}