$\newcommand{\Cat}{{\rm Cat}}$ $\newcommand{\A}{\mathcal A}$ $\newcommand{\freestar}{ \framebox[7pt]{\star} }$

## 2. Spin Glasses

1. ### Balanced colorings past criticality

Suppose we begin with an empty graph $G_0$, and we take a sequence of graphs $G_0,\ldots,G_{T}$ where to obtain $G_{t+1}$ from $G_t$ we add a random edge which maintains the property that $G_{t+1}$ is three-colorable.

#### Problem 2.1.

[Eyal Lubetzky] Does there exist a feasible coloring for the final graph, $G_T$, which is imbalanced, so that one color class has size at least $(\frac{1}{3} + \epsilon)n$ for some constant $\epsilon > 0$?
• #### Problem 2.2.

[Allan Sly] Is the satisfiability threshold equal to the reconstruction threshold on trees for your favorite model or random CSP?
• #### Problem 2.3.

[?] Suppose that $A$ is the adjacency matrix of a $d$-regular random graph, and let $X \subset \{-1,1\}^n$ be the subset of balanced sign vectors, $X = \{x \in \{-1,1\}^n ~|~ \sum_i x_i = 0\}$.

Prove that $\max_{x \in X} \frac{1}{n} x^\top A x = -\min_{x\in X} \frac{1}{n} x^\top A x + o(1).$

Alternatively, prove that $\lim_{n\to\infty}\max_{x \in X} \frac{1}{n} x^\top A x$ exists.

Cite this as: AimPL: Phase transitions in randomized computational problems, available at http://aimpl.org/phaserandom.