Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.21429 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- We consider the following problem: let $n>k$ be natural numbers, and let $G$ be a graph on $n$ vertices (undirected, without loops or multiple edges). Denote by $h_k(G)$ the number of unordered pairs of vertices in the graph $G$ whose degrees differ by less than $k$. We aim to determine the smallest possible value $f(n,k)$ of the quantity $h_k(G)$. Interest in this question is motivated by the fact that the bipartite analogue of the problem enabled S. Cichomski and F. Petrov to prove the Burdzy -- Pitman conjecture on the spread of independent coherent random variables. The problem has been solved under a number of restrictions on $n$ and $k$. A conjecture about the answer in the general case is also presented.