Abstract:
Connection between intersection graphs and homogeneous bent functions are studied. Let $\Gamma_{(n,k)}$ be a graph in which the vertices correspond to $\binom nk$ unordered subsets of size $k$ of a set $\{1,\dots,n\}$. Two vertices of $\Gamma_{(n,k)}$ are joined by an edge whenever the corresponding $k$-sets intersect in a subset of size one. Those $n$ and $k$ for which the graph $\Gamma_{(n,k)}$ has cliques of size $k+1$ are chosen. It is conjectured that, for such $n$ and $k$, the cliques of size $k+1$ in $\Gamma_{(n,k)}$ are maximal. It is shown that the number of cliques of size $k+1$ in the graph $\Gamma_{(n, k)}$ with $n=(k+1)k/2$ is equal to $n!/(k+1)!$. There are homogeneous Boolean functions in $10$ and $28$ variables which are obtained by taking complements to the cliques of the maximal size in the graphs $\Gamma_{(10,4)}$ and $\Gamma_{(28,7)}$ and which aren't bent functions.
Keywords:intersection graphs, homogeneous bent functions.