Combinatorial Designs, Difference Sets, and Bent Functions as Perfect Colorings of Graphs and Multigraphs

Сибирский математический журнал

article

V. N. Potapov¹  S. V. Avgustinovich¹ 

[1] Sobolev Institute of Mathematics

关键词: perfect coloring;    transversals of a hypergraph;    combinatorial designs;    q-analogs of combinatorial designs;    difference sets;    bent functions;    Johnson graph;    Grassmann graph;    Delsarte–Hoffman bound;   

DOI  :  10.1134/S0037446620050109

学科分类：数学（综合）

来源: Izdatel stvo Instituta Matematiki Rossiiskoi Akademii Nauk

【 摘 要 】

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.

【 授权许可】

CC BY