The Quantum Chromatic Number of the G₁₉ Join Family

Abstract

In Section 4.2 of Quantum Colorings of Spheres, Olivier Lalonde proposed \(G_n=G_{19}\vee K_{n-3}\) as a family of finite witnesses for his complex-sphere obstruction. Writing this family as \(J_n\) to reserve \(G_{19}\) for the fixed base graph, this note removes the rank-one restriction and proves

Here \(\xi\) denotes complex orthogonal rank. Consequently \(\xi(J_n)=n<\chi_q(J_n)=n+1\), confirming the proposed finite witnesses and giving an alternative finitary proof that \(\chi_q(S_{\mathbb C}^{n-1})\ge n+1\). Moreover, Lalonde's restricted parameters satisfy \(\chi_q^{[d]}(J_n)=\chi_q^{(s)}(J_n)=n+1\) for every \(d,s\ge1\). The \(n=3\) equality was already known; the new unrestricted cases begin with the 20-vertex apex graph \(H=G_{19}\vee K_1\), for which \(\chi_q(H)=5\).

1. Graph, conjecture, and theorem

The base graph has 19 vertices, 36 edges, graph6 record RxLAKA@AgYAWDGO?O?@??A?W@@OC@_, and exactly four triangles: \(123\), \(189\), \(345\), and \(267\). The symbol \(\vee\) denotes graph join and \(K_0\) is empty. This page writes \(J_n=G_{19}\vee K_{n-3}\) for the family Lalonde denotes \(G_n\), avoiding two meanings for \(G_{19}\) when \(n=19\).

Lalonde's Quantum Colorings of Spheres proposes this exact family as finite witnesses for his complex-sphere theorem, proves the rank-one value in Theorem 1.5, and states the full finite-dimensional equality as a conjecture immediately afterward.

For \(n=3\), \(J_3=G_{19}\) contains the Mančinska–Roberson graph \(G_{13}\), so \(\chi_q(J_3)=4\) was already known. The first new unrestricted case is \(J_4\); the proof treats every \(n\) uniformly.

The upper bound is classical: the note prints Lalonde's published four-coloring of \(G_{19}\), and every joined vertex receives a fresh color. The work is the dimension-independent lower bound. Since \(\xi(J_n)=n\) gives a homomorphism \(J_n\to S_{\mathbb C}^{n-1}\), monotonicity yields the finitary sphere consequence above. Lalonde's Proposition 3.3 explains why this finite witness cannot be extracted from the infinitary result by a general de Bruijn–Erdős principle.

2. Proof mechanism

Color uniformization

Starting from any putative quantum \(n\)-coloring in dimension \(d\), take the direct sum over all \(n!\) color permutations. The new dimension is \(D=n!d=nr\), with \(r=(n-1)!d>0\), and every projector has rank \(r\). This exactly absorbs zero outcomes, unequal original ranks, and reducibility.

Fixed-color corner and rational SOS

Each triangle joined with \(K_{n-3}\) is an \(n\)-clique. Clique-column saturation leaves, for each color, a \(3r\)-dimensional corner in which the four triangles partition the identity. For \(X=e_{10}+e_{11}+e_{12}+e_{13}\), three signed differences \(d_i\), and three Walsh forms \(H_i\), the graph relations imply

The left side has trace zero. Faithfulness of finite matrix trace makes all four factors vanish, and Walsh inversion yields the exact anticommutator system

Its support blocks are unitary, and a block-diagonal gauge puts vertices \(1,\ldots,13\) into the scalar sign-vector core tensored with an arbitrary multiplicity space \(K_c\cong\mathbb C^r\).

Exhaustive tail planes

The final six vertex ranges are classified by an arbitrary \(r\)-plane \(M_c\subset K_c\oplus K_c\) invariant under

Five tail-edge pullbacks are the identity and the sixth is \(-J_c\). Orthogonality gives inclusions in \(r\)-dimensional complements inside a \(2r\)-dimensional space, hence equalities. This proves exhaustiveness without a transversality assumption.

Cross-color sector packing

For two distinct colors, same-vertex orthogonality on the normalized core forces

The six tail compressions are \(\Omega_Y,\Omega_Z,-\Omega_X,\Omega_{Y+Z},\Omega_{Y-X},\Omega_{Z-X}\), where \(\Omega_L=\left(\begin{smallmatrix}0&L\\-L&0\end{smallmatrix}\right)\). They flip membership between \(M_c\) and \(M_d^\perp\). Splitting each \(J_c\)-invariant plane into its \(+i\) and \(-i\) sectors produces, for each sign, pairwise orthogonal physical subspaces across all colors.

If \(e_{c,+}+e_{c,-}=r\) are the two sector dimensions, those two packings require

Adding gives \(3nr\le2nr\), impossible for \(n,r>0\).

3. Why higher rank mattered

The known rank-one obstruction does not justify reducing arbitrary projector ranks to scalar rays. The new SOS proves the module-valued core directly. More importantly, a tail plane need not be the graph \(\operatorname{ran}(I,S)\) of an operator: nontransverse \(J\)-invariant planes occur, including planes that meet a coordinate axis. The proof retains every such branch and excludes only the simultaneous coexistence of all color representations in the physical space.

The rank-two plane \(M=\operatorname{span}\{(u,0),(0,u)\}\) is stronger than a nongraph example: its two sign-sector parameter spaces coincide. Their intersection dimension is preserved by the residual labeled-core gauge \(\operatorname{diag}(U,U,U)\), while scalar direct sums have orthogonal sign sectors. Thus fixed-color higher-rank representations are genuinely more general than scalar direct sums.

At rank one, \(M_c=\operatorname{span}(1,\sigma i)\), and the six tail frames reproduce Lalonde's Theorem 4.5 normal form exactly with \(b=\sigma\). The present derivation extends that classification without invoking its computer-assisted nonidentification lemma.

The proof directly addresses the three barriers Lalonde identifies at the end of Section 4.2: the SOS and \(J\)-invariant plane classify every fixed-color higher-rank branch; the cross-color plane flip and sector relations replace the role needed from Lemma 4.6; and the same rational identity and packing argument work for all \(n\), without large \(n\)-specific SDPs.

The induced subgraph on vertices \(1,\ldots,13\) is the Mančinska–Roberson \(G_{13}\). Their higher-rank proof that \(\chi_q(G_{13})=4\) is a relevant precedent; the present SOS, six-vertex tail classification, and cross-color packing use the additional structure of \(G_{19}\).

4. Exact verification and boundaries

Two independent standard-library obstruction verifiers accompany the proof, together with a separate graph checker:

• Short paper-form verifier with its certificate — replays the rational SOS, signs, six tail compressions, \(J\)-intertwining, and symbolic all-\(n\) dimension coefficients.
• Independent trace-SOS verifier with its certificate — also decodes graph6, checks clique witnesses, row-reduces the cross-color kernel, and verifies the all-\(n\) recurrence in \(\mathbb Q[n,f,d]\).
• Graph checker — reconstructs the graph, confirms no \(K_4\), validates Lalonde's four-coloring, and proves exhaustive non-three-colorability.
• Website file hashes — checksums for the PDFs and social-preview image served from this page.
• Revision audit and priority audit — record presentation decisions and the narrow post-proof literature check.

The programs use exact rational or integer arithmetic. The assertion-based tools explicitly reject Python's optimized mode, so stripped checks cannot produce a false PASS. The unitary gauge, projection/subspace and complement semantics, and final orthogonal-subspace packing remain human mathematics. These tools are algebraic replay, not a foundational proof assistant.

5. Scope and nonclaims

• The theorem is for the standard finite-dimensional quantum chromatic number \(\chi_q\).
• For every fixed \(d,s\ge1\), the restricted values \(\chi_q^{[d]}(J_n)\) and \(\chi_q^{(s)}(J_n)\) are also exactly \(n+1\).
• No result is claimed for \(\chi_{qa}\), \(\chi_{qc}\), infinite-dimensional strategies, or commuting-operator colorings.
• The proof allows zero projectors, nonuniform original ranks, reducible representations, and noncommuting projectors.
• It does not claim that each fixed-color higher-rank representation splits into rank-one representations; the non-graph tail planes show why that statement would be too strong.
• The narrow priority audit found no earlier proof, but that is not an absolute priority guarantee.
• The note has not been reviewed by a quantum-graph specialist or through formal peer review.

6. Context and references

• P. J. Cameron, A. Montanaro, M. W. Newman, S. Severini, and A. Winter, “On the Quantum Chromatic Number of a Graph,” Electronic Journal of Combinatorics 14(1), R81 (2007).
• O. Lalonde, “Quantum Colorings of Spheres,” arXiv:2606.10872v1 (2026).
• O. Lalonde, “On the Quantum Chromatic Numbers of Small Graphs,” Electronic Journal of Combinatorics 32(1), P1.18 (2025).
• L. Mančinska and D. E. Roberson, “Oddities of Quantum Colorings,” Baltic Journal on Modern Computing 4(4), 846–859 (2016).

AI-assisted research and verification

OpenAI language models were used extensively in exploration, proof development, software generation, verification design, literature organization, and drafting. Alec Kriebel directed the work, selected the released claims, and is responsible for the decision to publish these materials. Model output was not treated as evidence by itself; exact proofs and executable replay tools are provided for independent scrutiny.

Suggested citation

Alec Kriebel, “The Quantum Chromatic Number of the \(G_{19}\) Join Family,” research note, revised 2 August 2026. https://aleckriebel.github.io/Math/papers/lalonde-quantum-coloring/.