Estimability of coloured Gaussian graphical models: the smallest counterexample to the Forbes–Lauritzen bound

Abstract

Forbes and Lauritzen study the score matching estimator (SME) of a linear concentration model, a linear subspace L of the symmetric p × p matrices, and call L n-estimable when the SME exists with probability one, equivalently when det M(x)>0 for some sample x ∈ ℝ^(p × n). They prove that dim L>n(2p-n+1)/2 forces non-estimability, and conjecture the converse for the models S(N,E) of coloured graphs — the RCON models of Højsgaard and Lauritzen — where dim L=|N|+|E|. In its uncoloured form the conjecture is false: Gross and Sullivant refute it with K₄ plus a pendant vertex at n=3 on five vertices, and their rigidity criterion explains why. None of that theory reaches the coloured case, which the recent survey literature records as open. We settle its bottom layer. At n=1 the bound forces an uncoloured graph to have no edges at all, so the uncoloured conjecture is true there; with colours it is false on four vertices, and we exhibit two counterexamples with |N|+|E|=4=1 · (2 · 4-1+1)/2, one carrying a single edge and one connected (a coloured K₄). An exhaustive census of all coloured graphs on at most four vertices shows that no counterexample is smaller, in the number of vertices or in |N|+|E|. We also show that the hereditary strengthening of the conjecture — impose the count on every induced subgraph — fails on four vertices, where the simplest uncoloured witness named by Gross and Sullivant, the double banana, has eight. Every estimability verdict we prove is formally verified in Lean 4, and we say exactly which claims rest on exhaustive computation instead.

Open review

This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.

Archived files

1. Version 1 · current (opens in a new tab)

   Source snapshot 2026-09-07 03:53 UTC

   File fingerprint

   33542510a993fea3a9137c086552419f321fa1bbea22eb15105a5c16d6e2d44f