Positive Association in Random Proper Colorings

Definitions and mathematical statement

Let $G=(V,E)$ be a finite bipartite graph with specified parts $A$ and $B$, so that $V=A\sqcup B$ and every edge has one endpoint in each part. Let $q\in{\mathbb{N}}$ satisfy $q\geq3$, and use the color set $C_q=\{0,1,\ldots,q-1\}$. Define the finite set of proper colorings by \[ \Omega_q(G)=\{f:V\to C_q: f(u)\neq f(v)\text{ for every }uv\in E\}. \] This set is nonempty because $G$ is bipartite. Choose $f$ uniformly from $\Omega_q(G)$, and define \[ S=f^{-1}(\{0\})\cap A,\qquad \eta=(\mathbf{1}_{\{a\in S\}})_{a\in A}\in\{0,1\}^A. \] Equip $\{0,1\}^A$ with the coordinatewise partial order. A function $X:\{0,1\}^A\to{\mathbb{R}}$ is increasing if $X(x)\leq X(y)$ whenever $x_a\leq y_a$ for every $a\in A$. The random set $S$ has positive association if, for every pair of increasing functions $X,Y:\{0,1\}^A\to{\mathbb{R}}$, \[ {\mathbb{E}}[X(\eta)Y(\eta)]\geq{\mathbb{E}}[X(\eta)]\,{\mathbb{E}}[Y(\eta)], \] where expectations are taken over the uniform proper coloring.

The question is whether this inequality holds for every finite bipartite graph with specified parts $A,B$, every integer $q\geq3$, and every such pair $X,Y$. The supplied record labels this question open. Its background also mentions an unresolved four-vertex test, but does not specify that test; no additional formulation of it is asserted here.

Short English statement

For any finite bipartite graph and any integer $q\geq3$, choose a proper $q$-coloring uniformly. Must any two increasing real-valued functions of the set of vertices in $A$ colored $0$ have nonnegative covariance? The supplied open-status label and verification claims require independent human review.

Sources

• Local UnsolvedMath registry, permanent ID $30003338$, title "Positive Association in Random Proper Colorings," source problem code catalogue entry; collection: Oberwolfach Reports Open Problems. The record gives proposed year $2017$ and names no proposer.
• Supplied source citation: Combinatorics (2018), Oberwolfach Reports, DOI 10.4171/owr/2017/1, pp. 5--81, https://doi.org/10.4171/owr/2017/1. The supplied literature-sources entry labels this same link "original OWR report." Oberwolfach Reports is described in the record as documenting mathematical workshops and their open-problem discussions.
• Supplied literature assessment, checked 2026-08-21: the question is labeled open; the assessment says that the source report records the positive-association inequality as unknown, even for a four-vertex test, and that no later primary resolution of this exact question was located. The listed source checked is the original OWR report at https://doi.org/10.4171/owr/2017/1. This is supplied dated curation, not an independently verified literature assessment.
• The record carries statement status corrected_verified and reports that its clean statement was checked against the official Oberwolfach report and preserves the report's hypotheses, notation, and target. These are supplied verification claims; the source has not been independently consulted for this draft. The supplied citation's title year $2018$, DOI year component $2017$, and proposed year $2017$ are retained without resolving their relationship.