Orthogonal and unitary signings of cube-like graphs

Abstract

A unitary signing of a $d$-regular graph is a Hermitian adjacency matrix $M$ whose nonzero entries lie in $\{\pm1,\pm i\}$ and satisfies $M^2=dI$. Motivated by the work of Alon and Zheng on orthogonal and unitary signings of cube-like graphs, we introduce the $\Theta$-property for a generating set $S\subseteq\mathbb Z_2^n$: whenever three pairwise disjoint subsets of $S$ have the same sum, at least two of them have even size. We prove that every zero-free generating set with the $\Theta$-property gives a cube-like graph $Q_S$ admitting a unitary signing, and we give an explicit local formula for such a signing. For Sidon sets, the $\Theta$-property is also necessary, yielding a characterization of the Sidon cube-like graphs that admit unitary signings. In this setting there are exactly $2^{|S|-n}$ switching-equivalence classes of unitary signings, and we characterize when a unitary signing can be chosen to be orthogonal. The $\Theta$-property admits a linear-algebraic description in terms of the dependency space $\mathcal D$ of $S$: \[ |D_1\cap D_2| \equiv |D_1||D_2| \pmod2 \qquad (D_1,D_2\in\mathcal D). \] Equivalently, the map \[ D\longmapsto \binom{|D|}{2}\pmod2 \] is linear on $\mathcal D$. For the corresponding extremal set problem, in which zero is permitted, this formulation yields the sharp bound $|S|\leq 2n+1$ for generating sets with the $\Theta$-property. We give elementary constructions attaining this bound for every $n\geq3$. Under the additional Sidon condition, the same extremal value is attained for every $n\geq10$ using binary self-dual codes. The exact Sidon maximum is also determined for $3\leq n\leq9$.