Normality of G(n,p) with high probability
Open Question (normality of random graphs) · arXiv:1601.01129
Status open medium confidence
No paper resolving the question of whether G(n,p) random graphs are normal with high probability has been found. A related result (arXiv:1511.07591, predating this paper) proves that random d-regular graphs are a.a.s. normal for every fixed d, but this does not cover the G(n,p) model. The question, explicitly flagged as unresolved by the authors in 2016, remains open as of 2026.
Reviewer notes. arXiv:1511.07591 ('Almost All Regular Graphs are Normal', submitted November 2015) proves that for every fixed d, random d-regular graphs are a.a.s. normal, but explicitly does not address the Erdos-Renyi G(n,p) model. No post-2016 paper resolving or making major progress on the G(n,p) question was found. Confidence is medium rather than high because the conjecture is now ~10 years old, making absence of evidence in web search mildly suspicious.
Context
The authors note that partial motivation for studying normal graphs with small clique and independence numbers came from this question. They explicitly state that as of the time of writing this question 'is still unresolved.'
Notes. Stated in running prose without a labelled environment; explicitly flagged as unresolved by the authors.
Source paper
Minimal normal graph covers
David Gajser, Bojan Mohar · 2016-01-06
https://arxiv.org/abs/1601.01129
PDF source