Hypergram

A hypergram, introduced by Muller and Giorgetti (2025), is a triple in which is a finite hypergraph without isolated vertices or empty hyperedges and is a reduced simple graph on . Here, reduced means that has no isolated vertices or distinct vertices with identical neighborhoods. It is also required that

(1)

where two distinct vertices are adjacent in when they do not share a hyperedge of (Muller and Giorgetti 2025).

In the application to observable-based proofs of the Kochen-Specker theorem, the vertices represent nonidentity elements of an -qubit Pauli group, the hyperedges represent contexts of mutually commuting observables whose products are or , and adjacency in represents anticommutation. An -qubit Pauli assignment is an injective map from to the nonidentity Pauli observables that has exactly these commutation and context-product relations.

Let be the incidence matrix of , with rows indexed by vertices and columns by hyperedges, and let be the adjacency matrix of . Regard both as matrices over the finite field . A hypergram has a Pauli assignment iff

(2)

Equivalently, every hyperedge contains an even number of neighbors of each vertex. When these conditions hold, an assignment can be constructed in cubic time and the required number of qubits is

(3)

where denotes matrix rank (Muller and Giorgetti 2025).

Muller and Saniga (2026) define the hypergraph support of a reduced simple graph to consist of the nonempty independent sets for which

(4)

where is the incidence vector of . Every valid context family of a hypergram with anticommutation graph satisfies .

Each Pauli assignment gives every context a quantum sign according as its observable product is . A classical assignment instead gives the sign

(5)

The contextuality degree is the minimum Hamming distance

(6)

It is positive exactly when the assignment is contextual. The associated noncontextual bound and tolerated error per context are

(7)

respectively. These quantities depend only on the hypergram and not on the particular Pauli assignment (Muller and Giorgetti 2025).

Earlier work computed contextuality degrees for families of configurations in binary symplectic polar spaces (de Boutray et al. 2022) and tight noncontextual bounds for magic sets of observables (Trandafir, Lisonek, and Cabello 2022).

If is the line graph of a simple graph , every perfect matching of is a context in (Muller and Saniga 2026). Indeed, a perfect matching is an independent set in , while each vertex outside it has exactly two neighbors in it. This supplies many contexts for line graphs. In particular, gives the rook graph family beginning with the Peres-Mermin square, and gives the triangular graph family beginning with the doily configuration, namely the generalized quadrangle .

Under the assumptions that all contexts have the same size and every observable belongs to two contexts, the Peres-Mermin square and Mermin pentagram are the smallest observable-based proofs (Holweck and Saniga 2017).

Some exact contextuality values reported by Muller and Saniga (2026) are summarized below. The last row is a disjoint union of three copies of the Petersen graph; it is not a connected configuration.

anticommutation graph	configuration
	Peres-Mermin square	9	6	1
Petersen graph	Mermin pentagram	10	5	1
	doily	15	15	3
	connected configuration	25	120	36
	three Mermin pentagrams	30	215	76

The value in the last row was the largest exact value found in that search. The larger values listed there for and are only heuristic upper bounds on , not certified contextuality degrees.