RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika. Supplement // Archive

Prikl. Diskr. Mat. Suppl., 2018 Issue 11, Pages 52–53 (Mi pdma413)

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.

UDC: 519.7

DOI: 10.17223/2226308X/11/16



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025