Three Roles and One Bit: All Optimal Tables and Equality Graphs

Primarily AI-generated textHuman understanding: some partsmath.CO — Combinatoricsmath.PR — Probabilitycs.IT — Information Theory

Contributed by Viktor Diakin ↗

Version 1 / Nov 19, 2026 / CC BY 4.0

Abstract

We study a randomized one-bit fingerprint for distinguishing graphs on a common labeled vertex set. Each vertex independently receives one of three roles according to a common probability distribution. A symmetric Boolean table assigns bits to pairs of roles, and the fingerprint is the parity of these bits over the graph's edges. We prove that, for every n≥4n \geq 4, the optimal worst-case detection probability over all symmetric Boolean tables and role distributions is exactly 8/278/27. Every optimal distribution is uniform. For n≥5n \geq 5, we classify exactly 21 optimal tables with fixed role labels; one additional table is optimal when n=4n=4. We characterize all graphs attaining the minimum, up to isomorphism and isolated vertices: the four-cycle C4C_4 occurs for every optimal table, while the three-vertex path P3P_3 occurs additionally for 15 tables. For the canonical optimal table, we establish that the second distinct minimum is 80/24380/243 when n≥6n \geq 6, attained precisely by K2,4K_{2,4} with possible isolated vertices. For n=4,5n=4,5, the second minimum is 1/31/3. Our analytic proofs use homogeneous quadratic forms over the finite field F4\mathbb{F}_4, supported by reproducible exhaustive computations. The results also apply to differences of interlacement graphs associated with double-occurrence words.

Provenance statement

This research was initiated and coordinated by Viktor Diakin, an independent researcher. The mathematical investigation was conducted primarily with AI assistance. GPT-6.2 Astra Max developed the initial construction and minimax theorem. GPT-6 (Mira) contributed to the classification of optimal tables and computational checks. Further AI-assisted work developed the general proofs and equality classifications. The results were checked using reproducible Python computations. On November 18, 2026, Claude Sonnet 5.5 (Anthropic) independently examined the manuscript and reported no errors within the scope of its checks, including independently written computational tests. This does not constitute formal verification or human peer review. The human contributor coordinated the investigation, organized critical evaluations, preserved the research materials, and arranged independent verification. The manuscript is submitted with transparent disclosure of its AI-assisted origin.

Tools used

OpenAI
ChatGPTVersion GPT-6.2 Astra Max
OpenAI
ChatGPTVersion GPT-6
Anthropic
Claude SonnetVersion 5.5
Google
GeminiVersion Hydrogen (High)
DeepSeek
DeepSeek Chat

References

No bibliography entries.

Version history

  1. v1 · 11 pagesSubmitted by Viktor DiakinInitial depositCurrentNov 18, 2026