Normality Probability of Intermediate-Density Random Graphs

Definitions and mathematical statement

A finite simple graph $G=(V,E)$ is normal if it has a family $\mathcal Q$ of cliques and a family $\mathcal S$ of stable (independent) sets such that \[ \bigcup_{Q\in\mathcal Q}Q=V=\bigcup_{S\in\mathcal S}S, \qquad Q\cap S\ne\varnothing \quad\forall Q\in\mathcal Q,\ S\in\mathcal S. \] These are vertex covers by sets, not edge-clique covers or necessarily partitions. A clique and stable set can share at most one vertex, so each required intersection is exactly one point; maximality of the covering sets is not assumed.

The original question asks for the probability that a random graph with "middle edge density" is normal. The supplied clean reconstruction uses $G(n,p)$, the labeled graph on $\{1,\ldots,n\}$ with independent edge probability $p$, and interprets the density regime as \[ \exists\delta>0\ \forall n\text{ sufficiently large}:\qquad \delta\leq p_n\leq1-\delta. \] In that explicit interpretation the task is to determine the asymptotic behavior of \[ q_n(p_n)=\mathbb P\{G(n,p_n)\text{ is normal}\}. \] The record does not conjecture a particular limit. Fixed-$p$ limits, arbitrary admissible sequences $p_n$, a uniform result over $p\in[\delta,1-\delta]$, and a sharper asymptotic formula are different targets; existence of a common limit is not presumed. The source does not itself define the model or "middle", and the reconstruction is expressly unverified rather than an exact supplied hypothesis.

The literature triage checked 21 August 2026 discusses an incomplete normal-graph passage, later special classes and counterexamples, and no general resolution. Those structural results do not by themselves answer the random-graph normality probability. The original vague question, conservative reconstruction and dated literature limitations are retained separately.

Short English statement

What is the asymptotic probability of normality for a random graph at intermediate edge density? Normality means cross-intersecting vertex covers by cliques and stable sets. The $G(n,p)$ model with $p$ bounded away from zero and one is an explicitly unverified reconstruction, and no particular limit is supplied.

Sources

• Local UnsolvedMath registry, permanent ID 30000419, exact source code catalogue entry; Normality Probability of Intermediate-Density Random Graphs. Proposed year 2006, status open, statement_status reconstructed_unverified. The verification expressly identifies the bounded-away density formulation as an interpretation, not the report's explicit definition.
• Algorithmic Graph Theory (2006), Oberwolfach Reports, DOI 10.4171/owr/2006/07, pp. 379--460, https://doi.org/10.4171/owr/2006/07.
• Supplied literature triage checked 2026-08-21: "original OWR report", https://doi.org/10.4171/owr/2006/07; "normal-graph counterexample", https://doi.org/10.1016/j.jctb.2020.04.001. This dated OWR-derived curation requests independent verification of time-sensitive status and cited claims; it supplies no explicit probability asymptotic.