Про нові результати екстремальної теорії графiв, теорії алгебраїчних графів та їх застосування
DOI:
https://doi.org/10.15407/dopovidi2022.04.025Ключові слова:
сімейство графів великого обхвату, графи малого світу, криптографічнi алгоритми, LDPC кодиАнотація
Описано нові конструктивні приклади нескінченних сімейств графів малого світу та великого обхвату. Коротко оглянуто застосування цих об’єктів для побудови LDPC кодів та криптографічних алгоритмів. Визначено сімейства однорідних алгебраїчних графів великого обхвату над довільним комутативним кільцем К. Для кожного комутативного кільця цілісності K, |K| > 2, наведено сімейство дводольних однорідних алгебраїчних графів великого обхвату над К, утворене графами з многовидами точок і прямих, ізоморфними Kn, та цикловим показником ≥ 2n + 2. З цим сімейством пов’язано проєктивну границю графів, що є нескінченним лiсом.
Завантаження
Посилання
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.
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2022 Доповіді Національної академії наук України
Ця робота ліцензується відповідно до Creative Commons Attribution-NonCommercial 4.0 International License.
