×

Combinatorial designs, difference sets, and bent functions as perfect colorings of graphs and multigraphs. (English. Russian original) Zbl 1448.05028

Sib. Math. J. 61, No. 5, 867-877 (2020); translation from Sib. Mat. Zh. 61, No. 5, 1087-1100 (2020).
Summary: 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.

MSC:

05B30 Other designs, configurations
05C15 Coloring of graphs and hypergraphs
05C65 Hypergraphs
05D15 Transversal (matching) theory
05B20 Combinatorial aspects of matrices (incidence, Hadamard, etc.)
05B10 Combinatorial aspects of difference sets (number-theoretic, group-theoretic, etc.)
94A60 Cryptography
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Fon-Der-Flaass, DG, A bound on correlation immunity, Sib. Electr. Math. Reports, 4, 133-135 (2007) · Zbl 1132.05309
[2] Potapov, VN, On perfect 2-colorings of the \(q \)-ary \(n \)-cube, Discrete Math., 312, 6, 1269-1272 (2012) · Zbl 1245.05051 · doi:10.1016/j.disc.2011.12.004
[3] Avgustinovich, SV; Mogilnykh, IY, Perfect 2-colorings of Johnson graphs \(J(8,3)\) and \(J(8,4) \), J. Appl. Industr. Math., 17, 2, 3-19 (2010) · Zbl 1249.05242
[4] Fon-Der-Flaass, DG, Perfect 2-colorings of a hypercube, Sib. Math. J., 48, 4, 740-745 (2007) · Zbl 1164.05348 · doi:10.1007/s11202-007-0075-4
[5] Godsil, C.; Meagher, K., Erdos-Ko-Rado Theorems: Algebraic Approaches (2016), Cambridge: Cambridge Univ., Cambridge · Zbl 1343.05002
[6] Krotov, DS; Mogilnykh, IY; Potapov, VN, To the theory of \(q \)-ary Steiner and other-type trades, Discrete Math., 339, 3, 1150-1157 (2016) · Zbl 1328.05025 · doi:10.1016/j.disc.2015.11.002
[7] Glock, S.; Kühn, D.; Lo, A.; Osthus, D., The Existence of Designs (2019)
[8] Keevash, P., The Existence of Designs via Iterative Absorption: Hypergraph \(F \)-Designs for Arbitrary \(F (2020)\)
[9] Braun, M.; Etzion, T.; Östergard, PRJ; Vardy, A.; Wassermann, A., Existence of \(q \)-analogs of Steiner systems, Forum Math. Pi, 4, e7 (2016) · Zbl 1372.51003 · doi:10.1017/fmp.2016.5
[10] Ma, SL, A survey of partial difference sets, Des. Codes Cryptogr., 4, 4, 221-261 (1994) · Zbl 0798.05008 · doi:10.1007/BF01388454
[11] Mesnager, S., Bent Functions: Fundamentals and Results (2016), Cham, Switzerland: Springer, Cham, Switzerland · Zbl 1364.94008
[12] McFarland, RL, A family of difference sets in non-cyclic groups, J. Combin. Theory Ser. A, 15, 1, 1-10 (1973) · Zbl 0268.05011 · doi:10.1016/0097-3165(73)90031-9
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.