|
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 Γ(n,k).
The graph Γ(n,k) is the graph whose vertices correspond to (nk) unordered subsets of size k of the set {1,…,n}.
Two vertices of Γ(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 Γ(n,k) are identified.
We obtain a formula for the number of cliques of size k+1 in Γ(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 Γ(10,4) and Γ(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: | 278 | Full-text PDF : | 140 | References: | 37 | First page: | 7 |
|