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,λ) 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,λ)-designs and the Grassmann graph J2(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.
The first author was partly supported by the Russian Science Foundation (Grant 18–11–00136)
(Sections 1–3).
The second author was partly supported by the Basic Scientific Research of the Siberian Branch
of the Russian Academy of Sciences I.5.1 (Project 0314–2019–0016) (Sections 4–6).
Citation:
V. N. Potapov, S. V. Avgustinovich, “Combinatorial designs, difference sets, and bent functions as perfect colorings of graphs and multigraphs”, Sibirsk. Mat. Zh., 61:5 (2020), 1087–1100; Siberian Math. J., 61:5 (2020), 867–877