On new results on extremal graph theory, theory of algebraic graphs, and their applications
DOI:
https://doi.org/10.15407/dopovidi2022.04.025Keywords:
family of graphs of large girth, small world graphs, cryptographic algorithms, LDPC codesAbstract
New explicit constructions of infinite families of finite small world graphs of large girth with well-defined projective limits which is an infinite tree are described. The applications of these objects to constructions of LDPC codes and cryptographic algorithms are shortly observed. We define families of homogeneous algebraic graphs of large girth over the commutative ring K. For each commutative integrity ring K with |K| > 2, we introduce a family of bipartite homogeneous algebraic graphs of large girth over K formed by graphs with sets of points and lines isomorphic to Kn, n > 1, and cycle indicator ≥ 2n + 2 such that their projective limit is well defined and isomorphic to an infinite forest.
Downloads
References
Margulis, G. A. (1988). Explicit group-theoretical constructions of combinatorial schemes and their application to the desighn of expanders and concentrators. Problems Inform. Transmission, 24, No. 1, pp. 39-46.
Lubotzky, A., Phillips, R. & Sarnak, P. (1988). Ramanujan graphs. Combinatorica, 8, No. 3, pp. 261-277. https: //doi. org/10. 1007/BF02126799
Lazebnik, F., Ustimenko, V. A. & Woldar, A. J. (1995). New series of dense graphs of high girth. Bull. Amer. Math. Soc., 32, pp. 73-79. https: //doi. org/10. 1090/S0273-0979-1995-00569-0
Ustimenko, V. А. (2013). On the extremal graph theory and symbolic computations. Dopov. Nac. akad. nauk Ukr., No. 2, pp. 42-49 (in Russian).
Shaska, T. & Ustimenko, V. (2009). On the homogeneous algebraic graphs of large girth and their applications. Linear Algebra Appl., 430, No. 7, pp. 1826-1837. https: //doi. org/10. 1016/j. laa. 2008. 08. 023
Ustimenko, V. (1989). Affine system of roots and Tits geometries. Voprosy teorii grupp i gomologicheskoy algebry, Yaroslavl, pp. 155-157 (in Russian).
Lazebnik, F. & Ustimenko, V. (1993). Some algebraic constractions of dense graphs of large girth and of large size. DIMACS Series in Discrete Mathematics and Theoretical Computer Science (Vol. 10) (pp. 75-93). Providence: Amer. Math. Soc. https: //doi. org/10. 1090/dimacs/010/07
Lazebnik, F., Ustimenko, V. A. & Woldar, A. J. (1996). A characterisation of the components of the graphs D(k, q). Discrete Math., 157, pp. 271-283. https: //doi. org/10. 1016/S0012-365X(96)83019-6
Ustimenko, V. A. (2007). On linguistic dynamical systems, families of graphs of large girth, and cryptography. J. Math. Sci., 140, No. 3, pp. 461-471. https: //doi. org/10. 1007/s10958-007-0453-2
Ustimenko, V. & Romańczuk, U. (2013). On dynamical systems of large girth or cycle indicator and their applications to multivariate cryptography. In Artificial intelligence, evolutionary computing and metaheuristics. Studies in Computational Intelligence (Vol. 427) (pp. 231-256). Berlin, Heidelberg: Springer. https: //doi. org/10. 1007/978-3-642-29694-9_10
Polak, M. & Ustimenko, V. (2012, September). On LDPC codes corresponding to infinite family of graphs A(k, K). Proceedings of the Federated Conference on Computer science and information systems (FedCSIS) (pp. 11-23), Wroclaw.
MacKay, D. J. C. & Postol, M. S. (2003). Weaknesses of Margulis and Ramanujan-Margulis low-dencity parity-check codes. Electron. Notes Theor. Comput. Sci., 74, pp. 97-104. https: //doi. org/10. 1016/S1571-0661(04)80768-0
Ustimenko, V. (2021). On semigroups of multivariate transformations constructed in terms of time dependent linguistic graphs and solutions of Post Quantum Multivariate Cryptography. Cryptology ePrint Archive: Report 2021/1466. Retrieved from https: //eprint. iacr. org/2021/1466. pdf
Ustimenko, V. A. (1998). Coordinatization of regular tree and its quotients. In Voronoi’s impact on modern science (Vol. 2) (pp. 125-152). Kyiv: Institute of Mathematics.
Ustimenko, V. A. (2009). Algebraic groups and small world graphs of high girth. Albanian J. Math., 3, No. 1, pp. 25-33.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2022 Reports of the National Academy of Sciences of Ukraine
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
