Submitted works

Advanced search

math.CO — Combinatorics

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

Contributed by Viktor Diakin

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.

Primarily AI-generated textHuman understanding: some partsCombinatoricsMinimax optimizationRandomized fingerprintingcoding theoryfinite fieldsgraph theory
Nov 19, 202611 pages
PDFView work