RUS  ENG
Full version
JOURNALS // Sibirskii Matematicheskii Zhurnal // Archive

Sibirsk. Mat. Zh., 2020 Volume 61, Number 5, Pages 1087–1100 (Mi smj6039)

This article is cited in 5 papers

Combinatorial designs, difference sets, and bent functions as perfect colorings of graphs and multigraphs

V. N. Potapov, S. V. Avgustinovich

Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk

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.

UDC: 519.17+519.14

MSC: 35R30

Received: 18.02.2020
Revised: 16.03.2020
Accepted: 08.04.2020

DOI: 10.33048/smzh.2020.61.510


 English version:
Siberian Mathematical Journal, 2020, 61:5, 867–877

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025