|
Relationship between homogeneous bent functions and Nagy graphs
A. S. Shaporenkoab a Novosibirsk State University, 2 Pirogov Street, 630090, Novosibirsk, Russia
b JetBrains Research, 1 Pirogov Street, 630090, Novosibirsk, Russia
Abstract:
We study the relationship between homogeneous bent functions and some intersection graphs of a special type
that are called Nagy graphs and denoted by $\Gamma_{(n,k)}$.
The graph $\Gamma_{(n,k)}$ is the graph whose vertices correspond to $\binom{n}{k}$ unordered subsets of size $k$ of the set $\{1,\dots,n\}$.
Two vertices of $\Gamma_{(n,k)}$ are joined by an edge whenever the corresponding $k$-sets have exactly one common element.
Those $n$ and $k$ for which the cliques of size $k+1$ are maximal in $\Gamma_{(n, k)}$ are identified.
We obtain a formula for the number of cliques of size $k+1$ in $\Gamma_{(n, k)}$ for $n=(k+1)k/2$.
We prove that homogeneous Boolean functions of $10$ and $28$ variables obtained by taking the complement to the cliques
of maximal size in $\Gamma_{(10,4)}$ and $\Gamma_{(28,7)}$ respectively are not bent functions. Tab. 3, illustr. 2, bibliogr. 9.
Keywords:
intersection graph, Nagy graph, homogeneous bent function, maximal clique.
Received: 25.02.2019 Revised: 01.08.2019 Accepted: 28.08.2019
Citation:
A. S. Shaporenko, “Relationship between homogeneous bent functions and Nagy graphs”, Diskretn. Anal. Issled. Oper., 26:4 (2019), 121–131
Linking options:
https://www.mathnet.ru/eng/da940 https://www.mathnet.ru/eng/da/v26/i4/p121
|
Statistics & downloads: |
Abstract page: | 234 | Full-text PDF : | 123 | References: | 18 | First page: | 7 |
|