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,\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.
Keywords:intersection graph, Nagy graph, homogeneous bent function, maximal clique.
Fulltext:
PDF file (326 kB)