Relationship between homogeneous bent~functions and Nagy graphs

A. S. Shaporenko

Diskretnyj analiz i issledovanie operacij, Tome 26 (2019) no. 4, pp. 121-131.

Résumé

We study the relationship between homogeneous bent functions and some intersection graphs of a special type that are called Nagy graphs and denoted by ${\mathrm{\Gamma }}_{(n,k)}$. The graph ${\mathrm{\Gamma }}_{(n,k)}$ is the graph whose vertices correspond to $(\genfrac{}{}{0ex}{}{n}{k})$ unordered subsets of size $k$ of the set $\{1,\dots ,n\}$. Two vertices of ${\mathrm{\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 ${\mathrm{\Gamma }}_{(n,k)}$ are identified. We obtain a formula for the number of cliques of size $k+1$ in ${\mathrm{\Gamma }}_{(n,k)}$ for $n=(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 ${\mathrm{\Gamma }}_{(10,4)}$ and ${\mathrm{\Gamma }}_{(28,7)}$ respectively are not bent functions. Tab. 3, illustr. 2, bibliogr. 9.

Détail

Mots-clés : intersection graph, Nagy graph, homogeneous bent function, maximal clique.

Bibliographie

[1] O. S. Rothaus, “On “bent” functions”, J. Comb. Theory., Ser. A, 20:3 (1976), 300–305 | DOI | MR | Zbl

[2] C. Qu, J. Seberry, J. Pieprzyk, “Homogeneous bent functions”, Discrete Appl. Math., 102:1-2 (2000), 133–139 | DOI | MR | Zbl

[3] C. Charnes, M. Rotteler, T. Beth, “Homogeneous bent functions, invariants, and designs”, Des., Codes Cryptogr., 26:1-2 (2002), 139–154 | DOI | MR | Zbl

[4] A. Bernasconi, B. Codenotti, “Spectral analysis of Boolean functions as a graph eigenvalue problem”, IEEE Trans. Comput., 48:3 (1999), 345–351 | DOI | MR | Zbl

[5] A. Bernasconi, B. Codenotti, J. M. Vanderkam, “A characterization of bent functions in terms of strongly regular graphs”, IEEE Trans. Comput., 50:9 (2001), 984–985 | DOI | MR | Zbl

[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., 2014, no. 3, 28–39 (Russian)

[7] N. A. Kolomeec, “On connectivity of the minimal distance graph for the set of bent functions”, Prikl. Diskretn. Mat., Suppl., 2015, no. 8, 33–34 (Russian)

[8] E. P. Korsakova, “Some classification of the graphs for quadratic bent functions of 6 variables”, Diskretn. Anal. Issled. Oper., 20:5 (2013), 45–47 (Russian) | MR

[9] N. N. Tokareva, Bent functions: results and applications to cryptography, Acad. Press, Amsterdam, 2015, 220 pp. | MR | Zbl