2. Spin Glasses

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 threecolorable.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.