TY - JOUR

T1 - Relationship Between Homogeneous Bent Functions and Nagy Graphs

AU - Shaporenko, A. S.

N1 - Funding Information: The author was supported by the Russian Foundation for Basic Research (project no. 18-07- 01394) and the Ministry of Science and Higher Education of the Russian Federation (Contract no. 1.13559.2019/13.1 and the Programme 5-100). Publisher Copyright: © 2019, Pleiades Publishing, Ltd.

PY - 2019/10/1

Y1 - 2019/10/1

N2 - 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.

AB - 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.

KW - homogeneous bent function

KW - intersection graph

KW - maximal clique

KW - Nagy graph

UR - http://www.scopus.com/inward/record.url?scp=85078927961&partnerID=8YFLogxK

UR - https://elibrary.ru/item.asp?id=43243231

U2 - 10.1134/S1990478919040173

DO - 10.1134/S1990478919040173

M3 - Article

AN - SCOPUS:85078927961

VL - 13

SP - 753

EP - 758

JO - Journal of Applied and Industrial Mathematics

JF - Journal of Applied and Industrial Mathematics

SN - 1990-4789

IS - 4

M1 - 17

ER -