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!
|
| _version_ | 1866914255305965568 |
|---|---|
| author | Onishchenko, Sergey Dmitrievich |
| author_facet | Onishchenko, Sergey Dmitrievich |
| 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_21429 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Maximum Spread of Vertex Degrees in a Simple Graph Onishchenko, Sergey Dmitrievich Combinatorics 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. |
| title | Maximum Spread of Vertex Degrees in a Simple Graph |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2509.21429 |