Bisections of large random sparse regular graphs (problems 32 and 33)

Let $G_d$ be a uniformly random $d$-regular graph on $n$, an even number of nodes. Throughout this post we will think of $d$ as a fixed constant and are interested in understanding the setting in which $n$ is very large. The graphs will be simple and undirected.

Let $A$ be the $n\times n$ adjacency matrix of a graph $G$. Given a set of nodes $S\subset[n]$ we denote by $\mathrm{cut}(S)=\sum_{i\in S}\sum_{i\notin S}A_{ij}$ the number of edges between $S$ and its complement. We will be interested in three different quantities:

Definition:

For $G$ a simple undirected graph we define:

\[\mathrm{MinBis}(G) = \min_{S\subset [n],\ |S|=\frac{n}2} \mathrm{cut}(S),\]

\[\mathrm{MaxBis}(G) = \max_{S\subset [n],\ |S|=\frac{n}2} \mathrm{cut}(S),\]

\[\mathrm{MaxCut}(G) = \max_{S\subset [n]} \mathrm{cut}(S).\]

We will be interested in understanding the expected value of these quantities for fixed $d$ and as $n$ grows. The following inequalities are easy to check:

\(\frac1n\mathbb{E}\,\mathrm{MinBis}(G_d) \leq \frac{d}4+o(1) \leq \frac1n\mathbb{E}\,\mathrm{MaxBis}(G_d) \leq \frac1n\mathbb{E}\,\mathrm{MaxCut}(G_d),\) by noting the expected value of an average bisection is given by $\mathbb{E}\,\mathrm{cut}([n/2]) = \frac{dn}{4}\frac{n}{n-1}=n\left(\frac{d}4+o(1)\right)$, where $o(1)$ is a quantity that tends to $0$ as $n\to\infty$.

There is a beautiful conjecture of Zdeborova and Boettcher (Zdeborová & Boettcher, 2010) that says that the deviation from the average cut is the same for all three quantities. We state it below precisely (in two separate equalities).

Conjecture 32 (Min and Max Bisections)

Let $G_d$ be a uniformly random $d$-regular graph on $n$ nodes ($n$ even). We have, for any $d\geq 3$: \(\frac1n\mathbb{E}\,\mathrm{MinBis}(G_d) + \frac1n\mathbb{E}\,\mathrm{MaxBis}(G_d) = \frac{d}2+o(1).\)

Conjecture 33 (Max Cut and Max Bisections)

Let $G_d$ be a uniformly random $d$-regular graph on $n$ nodes ($n$ even). We have, for any $d\geq 3$: \(\frac1n\mathbb{E}\,\mathrm{MaxCut}(G_d) = \frac1n\mathbb{E}\,\mathrm{MaxBis}(G_d) + o(1).\)

Dembo, Montanari, and Sen (Dembo et al., 2017) have shown that this is true up to $o_d(\sqrt{d})$ (where here the $o_d(\cdot)$ is meant as $d\to\infty$). By connecting this problem to the celebrated Sherrington–Kirkpatrick model (discussed in post 7 of this blog) they showed that the three quantities are, for large $d$, equal to $\frac{d}{4}\pm P_\ast\sqrt{\frac{d}{4}} + o_d(\sqrt{d}) + o(1)$, where $P_\ast$ is the celebrated Parisi constant from Statistical Physiics ($P_\ast\approx 0.76$). Furthermore, recently (Coja-Oghlan et al., 2022) new upper bounds on the MaxCut quantity have been established.

References

1. Zdeborová, L., & Boettcher, S. (2010). A conjecture on the maximum cut and bisection width in random regular graphs. Journal of Statistical Mechanics: Theory and Experiment, 2010(02), P02020. https://doi.org/10.1088/1742-5468/2010/02/P02020
2. Dembo, A., Montanari, A., & Sen, S. (2017). Extremal cuts of sparse random graphs. The Annals of Probability, 45(2), 1190–1217.
3. Coja-Oghlan, A., Loick, P., Mezei, B. F., & Sorkin, G. B. (2022). The Ising Antiferromagnet and Max Cut on Random Regular Graphs. SIAM Journal on Discrete Mathematics, 36(2), 1306–1342. https://doi.org/10.1137/20M137999X