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 $\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,\dots,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=(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.

Détail

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