Connection between homogeneous bent functions and intersection graphs

Connection between intersection graphs and homogeneous bent functions are studied. Let Г(_{п к}) be a graph in which the vertices correspond to ^^ unordered subsets of size k of a set {1,..., n}. Two vertices of Г(_{п к}) 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 Г(_п,_к) has cliques of size k + 1 are chosen. It is conjectured that, for such n and k, the cliques of size k + 1 in Г(_пк) are maximal. It is shown that the number of cliques of size k + 1 in the graph Г(_пк) 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 Г(₁₀,₄) and Г(₂8,7) and which aren't bent functions.

Keywords

Authors

References