Geodesic
Relationship between homogeneous bent functions and Nagy graphs
Diskretnyj analiz i issledovanie operacij, Tome 26 (2019) no. 4, pp. 121-131 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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
Mots-clés : maximal clique. 
@article{DA_2019_26_4_a6,
     author = {A. S. Shaporenko},
     title = {Relationship between homogeneous bent~functions and {Nagy} graphs},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {121--131},
     year = {2019},
     volume = {26},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2019_26_4_a6/}
}
TY  - JOUR
AU  - A. S. Shaporenko
TI  - Relationship between homogeneous bent functions and Nagy graphs
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2019
SP  - 121
EP  - 131
VL  - 26
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DA_2019_26_4_a6/
LA  - ru
ID  - DA_2019_26_4_a6
ER  - 
%0 Journal Article
%A A. S. Shaporenko
%T Relationship between homogeneous bent functions and Nagy graphs
%J Diskretnyj analiz i issledovanie operacij
%D 2019
%P 121-131
%V 26
%N 4
%U http://geodesic.mathdoc.fr/item/DA_2019_26_4_a6/
%G ru
%F DA_2019_26_4_a6
A. S. Shaporenko. Relationship between homogeneous bent functions and Nagy graphs. Diskretnyj analiz i issledovanie operacij, Tome 26 (2019) no. 4, pp. 121-131. http://geodesic.mathdoc.fr/item/DA_2019_26_4_a6/

[1] O. S. Rothaus, “On “bent” functions”, J. Comb. Theory., Ser. A, 20:3 (1976), 300–305 | DOI | MR | Zbl

[2] C. Qu, J. Seberry, J. Pieprzyk, “Homogeneous bent functions”, Discrete Appl. Math., 102:1-2 (2000), 133–139 | DOI | MR | Zbl

[3] C. Charnes, M. Rotteler, T. Beth, “Homogeneous bent functions, invariants, and designs”, Des., Codes Cryptogr., 26:1-2 (2002), 139–154 | DOI | MR | Zbl

[4] A. Bernasconi, B. Codenotti, “Spectral analysis of Boolean functions as a graph eigenvalue problem”, IEEE Trans. Comput., 48:3 (1999), 345–351 | DOI | MR | Zbl

[5] A. Bernasconi, B. Codenotti, J. M. Vanderkam, “A characterization of bent functions in terms of strongly regular graphs”, IEEE Trans. Comput., 50:9 (2001), 984–985 | DOI | MR | Zbl

[6] N. A. Kolomeec, “An upper bound for the number of bent functions at distance $2^k$ from an arbitrary bent function of 2k variables”, Prikl. Diskretn. Mat., 2014, no. 3, 28–39 (Russian)

[7] N. A. Kolomeec, “On connectivity of the minimal distance graph for the set of bent functions”, Prikl. Diskretn. Mat., Suppl., 2015, no. 8, 33–34 (Russian)

[8] E. P. Korsakova, “Some classification of the graphs for quadratic bent functions of 6 variables”, Diskretn. Anal. Issled. Oper., 20:5 (2013), 45–47 (Russian) | MR

[9] N. N. Tokareva, Bent functions: results and applications to cryptography, Acad. Press, Amsterdam, 2015, 220 pp. | MR | Zbl