Cospectral Boolean Sensitivity Graphs Can Have Different Global Geometry: An Exact Separation and Infinite Family

Boolean functions are commonly compared through scalar complexity measures such as sensitivity, block sensitivity, certificate complexity, polynomial degree, and deterministic decision-tree depth. Spectral information from hypercube-derived graphs provides a richer control, but it remains unclear how much global sensitivity geometry such summaries determine. We show that even a strengthened collection of Boolean complexity measures together with the complete adjacency spectrum does not determine the connected-component geometry of the sensitivity graph. An exhaustive search of all (³²₅) = 201,376 five-variable truth sets with five positive inputs yields an explicit pair of Boolean functions that agree in essential-variable count, sensitive-edge count, maximum sensitivity, sensitivity-degree histogram, sorted directional sensitivity counts, block sensitivity, deterministic decision-tree depth, certificate complexity, GF(2) degree, and real multilinear degree. Their active sensitivity graphs are exactly adjacency-cospectral, as certified by equality of their integer characteristic polynomials, yet their active component sizes are (16, 4) versus (11, 9) and their diameter profiles are (6, 2) versus (4, 4). We then lift the pair by XOR with parity on fresh variables. The lift preserves equality of the matched complexity controls and exact cospectrality while retaining different component-size and diameter profiles, producing a separation in every essential dimension N ≥ 5. Thus standard Boolean complexity information, even augmented by the full adjacency spectrum, does not determine global sensitivity-graph geometry.