Phase transitions in randomized computational problems

$\newcommand{\Cat}{{\rm Cat}}$

$\newcommand{\A}{\mathcal A}$

$\newcommand{\freestar}{ \framebox[7pt]{$\star$} }$

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 three-colorable.

Add remark

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$ ?
Add remark

Problem 2.2.
[Allan Sly] Is the satisfiability threshold equal to the reconstruction threshold on trees for your favorite model or random CSP?
Add remark

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.