| Register
\(\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.

      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.