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 Γ_(n,k). The graph Γ_(n,k) is the graph whose vertices correspond to (n_k) unordered subsets of size k of the set 1,..., n. Two vertices of Γ(_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 Γ_(n,k) are identified. We obtain a formula for the number of cliques of size k + 1 in Γ(_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 Γ(₁₀,4) and Γ_(28,7) respectively are not bent functions.