Connection between homogeneous bent functions and intersection graphs

A. S. Shaporenko

Prikladnaya Diskretnaya Matematika. Supplement, no. 11 (2018), pp. 52-53.

Résumé

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.

Détail

Keywords: intersection graphs, homogeneous bent functions.

Bibliographie

[1] Charnes C., Rotteler M., Beth T., “Homogeneous bent functions, invariants, and designs”, Designs, Codes and Cryptography, 26 (2002), 139–154 | DOI | MR | Zbl

[2] Qu C., Seberry J., Pieprzyk J., “Homogeneous bent functions”, Discrete Appl. Math., 102:1–2 (2000), 133–139 | MR | Zbl