Non-zero P_G coefficient in random 4-regular graphs
Problem 2.1 · arXiv:2511.02892
Status open high confidence
Problem 2.1 asks whether the graph polynomial $P_G = \prod_{uv \in E(G)}(u-v)$ for a random 4-regular graph has a.a.s. non-zero coefficient at $\prod_{v \in V(G)} v^2$; by the Alon-Tarsi method this would imply that random 4-regular graphs are a.a.s. 3-choosable. The paper notes the expected value of the coefficient is zero in the two-Hamiltonian-cycles model, so any proof requires an anti-concentration inequality. No follow-up paper resolving this problem was found in the literature as of May 2026.
Reviewer notes. No follow-up found. The problem is closely related to the Alon-Tarsi method: a non-zero coefficient at $\prod_v v^2$ is equivalent to the number of even Eulerian subgraphs differing from the number of odd Eulerian subgraphs (EE ≠ EO), which would establish a.a.s. 3-choosability of random 4-regular graphs. The paper explicitly flags that an anti-concentration inequality would be needed.
Context
The graph polynomial $P_G$ is uniform and every monomial appearing with a non-zero coefficient has total degree $|E(G)|$; for a 4-regular graph the only relevant monomial is $\prod_{v\in V(G)}v^{2}$. The expected value of the coefficient is zero in the two Hamiltonian cycles model, so a proof would require an anti-concentration inequality.
Source paper
Open problems of the 33rd Workshop on Cycles and Colourings
János Barát, Zdeněk Dvořák, Penny Haxell, František Kardoš, Borut Lužar, Alfréd Onderko, Jozef Rajník, Roman Soták, Nikolay Ulyanov · 2025-11-04
https://arxiv.org/abs/2511.02892