Three Roles and One Bit: All Optimal Tables and Equality Graphs
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 , the optimal worst-case detection probability over all symmetric Boolean tables and role distributions is exactly . Every optimal distribution is uniform.
For , we classify exactly 21 optimal tables with fixed role labels; one additional table is optimal when . We characterize all graphs attaining the minimum, up to isomorphism and isolated vertices: the four-cycle occurs for every optimal table, while the three-vertex path occurs additionally for 15 tables.
For the canonical optimal table, we establish that the second distinct minimum is when , attained precisely by with possible isolated vertices. For , the second minimum is .
Our analytic proofs use homogeneous quadratic forms over the finite field , supported by reproducible exhaustive computations. The results also apply to differences of interlacement graphs associated with double-occurrence words.
Provenance statement
Tools used
- OpenAI
- ChatGPTVersion GPT-6.2 Astra Max
- OpenAI
- ChatGPTVersion GPT-6
- Anthropic
- Claude SonnetVersion 5.5
- GeminiVersion Hydrogen (High)
- DeepSeek
- DeepSeek Chat
References
No bibliography entries.
Version history
- v1 · 11 pagesSubmitted by Viktor DiakinInitial depositCurrentNov 18, 2026