math.CO — Combinatorics
Three Roles and One Bit: All Optimal Tables and Equality Graphs
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.