Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2019, 13:4, 753-758
Volume 26, No 4, 2019, P. 121-131
UDC 519.7
A. S. Shaporenko
Relationship between homogeneous bent functions and Nagy graphs
Abstract:
We study the relationship between homogeneous bent functions and some intersection graphs of a special type that are called Nagy graphs and denoted by $\Gamma_{(n,k)}$. The graph $\Gamma_{(n,k)}$ is the graph whose vertices correspond to $\binom{n}{k}$ unordered subsets of size $k$ of the set {$1, . . . , n$}. Two vertices of $\Gamma_{(n,k)}$ are joined by an edge whenever the corresponding $k$-sets have exactly one common element. Those $n$ and $k$ for which the cliques of size $k + 1$ are maximal in $\Gamma_{(n,k)}$ are identified. We obtain a formula for the number of cliques of size $k + 1$ in $\Gamma_{(n,k)}$ for $n = \frac {(k+1)k} {2}$. We prove that homogeneous Boolean functions of 10 and 28 variables obtained by taking the complement to the cliques of maximal size in $\Gamma(10,4)$ and $\Gamma(28,7)$ respectively are not bent functions.
Tab. 3, illustr. 2, bibliogr. 9.
Keywords: intersection graph, Nagy graph, homogeneous bent function, maximal clique.
DOI: 10.33048/daio.2019.26.649
Aleksandr S. Shaporenko 1,2
1. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
2. JetBrains Research,
1 Pirogov Street, 630090, Novosibirsk, Russia
e-mail: shaporenko.alexandr@gmail.com
Received February 25, 2019
Revised August 1, 2019
Accepted August 28, 2019
References
[1] O. S. Rothaus, On “bent” functions, J. Comb. Theory , Ser. A 20 (3), 300–305 (1976).[2] C. Qu, J. Seberry, and J. Pieprzyk, Homogeneous bent functions, Discrete Appl. Math. 102 (1–2), 133–139 (2000).
[3] C. Charnes, M. Rotteler, and T. Beth, Homogeneous bent functions, invariants, and designs, Des. Codes Cryptogr. 26 (1–2), 139–154 (2002).
[4] A. Bernasconi and B. Codenotti, Spectral analysis of Boolean functions as a graph eigenvalue problem, IEEE Trans. Comput. 48 (3), 345–351 (1999).
[5] A. Bernasconi, B. Codenotti, and J. M. Vanderkam, A characterization of bent functions in terms of strongly regular graphs, IEEE Trans. Comput. 50 (9), 984–985 (2001).
[6] N. A. Kolomeec, An upper bound for the number of bent functions at distance $2^k$ from an arbitrary bent function of $2k$ variables, Prikl. Diskretn. Mat., No. 3, 28–39 (2014) [Russian].
[7] N. A. Kolomeec, On connectivity of the minimal distance graph for the set of bent functions, Prikl. Diskretn. Mat., Suppl., No. 8, 33–34 (2015) [Russian].
[8] E. P. Korsakova, Some classification of the graphs for quadratic bent functions of 6 variables, Diskretn. Anal. Issled. Oper. 20 (5), 45–47 (2013) [Russian].
[9] N. Tokareva, Bent Functions: Results and Applications to Cryptography (Acad. Press, Amsterdam, 2015).
