A combinatorial proof of the Burdzy-Pitman conjecture

Stanisław Cichomski; Fedor Petrov

paper

A combinatorial proof of the Burdzy-Pitman conjecture

arXiv:2204.07219

Abstract

We prove a sharp upper bound for the number of high degree differences in bipartite graphs: let $(U, V, E)$ be a bipartite graph with $U = {u_{1}, u_{2}, \dots, u_{n}}$ and $V = {v_{1}, v_{2}, \dots, v_{n}}$ ; for $n \geq k > \frac{n}{2}$ we show that $\sum_{1 \leq i, j \leq n} 1 {∣ deg (u_{i}) - deg (v_{j}) ∣ \geq k} \leq 2 k (n - k) .$ As a direct application we show a slightly stronger, probabilistic version of this theorem and thus confirm the Burdzy-Pitman conjecture about the maximal spread of coherent and independent distributions.