|
Discrete Functions
Connection between homogeneous bent functions and intersection graphs
A. S. Shaporenko Novosibirsk State University, Novosibirsk
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.
Citation:
A. S. Shaporenko, “Connection between homogeneous bent functions and intersection graphs”, Prikl. Diskr. Mat. Suppl., 2018, no. 11, 52–53
Linking options:
https://www.mathnet.ru/eng/pdma413 https://www.mathnet.ru/eng/pdma/y2018/i11/p52
|
Statistics & downloads: |
Abstract page: | 114 | Full-text PDF : | 20 | References: | 15 |
|