Abstract:
We prove that (1): the characteristic function of each independent set in each regular graph attaining the Delsarte–Hoffman bound is a perfect coloring; (2): each transversal in a uniform regular hypergraph is an independent set in the vertex adjacency multigraph of a hypergraph attaining the Delsarte–Hoffman bound for this multigraph; and (3): the combinatorial designs with parameters $t$-$(v,k,\lambda)$ and their $q$-analogs, difference sets, Hadamard matrices, and bent functions are equivalent to perfect colorings of some graphs of multigraphs, in particular, the Johnson graph $J(n,k)$ for $(k-1)$-$(v,k,\lambda)$-designs and the Grassmann graph $J_2(n,2)$ for bent functions.
Keywords:perfect coloring, transversals of a hypergraph, combinatorial designs, $q$-analogs of combinatorial designs, difference sets, bent functions, Johnson graph, Grassmann graph, Delsarte–Hoffman bound.