Combinatorial Designs, Difference Sets, and Bent Functions as Perfect Colorings of Graphs and Multigraphs
- PDF / 194,976 Bytes
- 11 Pages / 612 x 792 pts (letter) Page_size
- 3 Downloads / 218 Views
INATORIAL DESIGNS, DIFFERENCE SETS, AND BENT FUNCTIONS AS PERFECT COLORINGS OF GRAPHS AND MULTIGRAPHS V. N. Potapov and S. V. Avgustinovich
UDC 519.17:519.14
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. DOI: 10.1134/S0037446620050109 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
Introduction A coloring of a graph G = (V, E) is a function from the vertex set V (G) of G into a finite set I of colors. A coloring f is called perfect whenever the collections of vertices adjacent to the vertices of the same color have identical color composition. Formally this means the following: For every color i ∈ I and all x, y ∈ V (G), it ensues from f (x) = f (y) that |f −1 (i) ∩ S(x)| = |f −1 (i) ∩ S(y)|, where S(x) = {z ∈ V (G) : {z, x} ∈ E(G)} is the set of vertices adjacent to x. Also, the terms “equitable partition” and “partition design” are commonly used in the literature for the set {f −1 (i) : i ∈ I} which is a partition of the vertex set of G according to the colors of a perfect coloring. The matrix P = (pij ) of size |I| × |I| whose entry pij equals the number of vertices of color j adjacent to some vertex of color i is called the parameter matrix of the perfect coloring. Perfect colorings in two colors turn out to be solutions to extremal problems on graphs. The definition of 1-perfect code in an r-regular graphimplies directly that its characteristic function is a perfect 0 r coloring with parameter matrix . As [1] shows, all unbalanced Boolean functions reaching 1 r−1 the Fon-Der-Flaass correlation immunity bound are perfect colorings. The orthogonal arrays reaching the Bierbrauer–Friedman bound [2] also turn out to be perfect colorings. We have obtained another similar example. In Theorem 1 we establish that if an independent set in a regular graph attains the Delsarte–Hoffman bound then its characteristic function is a perfect coloring. This article suggests some description for various well-known combinatorial structures in terms of perfect colorings of simple graphs, as well as hypergraphs and multigraphs. Proposition 6 shows that we may regard a transversal of a uniform regular hypergraph as an independent set in some multigraph attaining the Delsarte–Hoffman bound and, consequently, as a perfect coloring. In Section 4 we The first author was
Data Loading...
