Про нові експандери необмеженого степеня для практичного застосування в інформатиці
DOI:
https://doi.org/10.15407/dopovidi2014.12.044Ключові слова:
інформатика, експандери необмеженого степеня, застосуванняАнотація
Розглянуто метод побудови нових прикладів родин графів-експандерів необмеженого степеня. Графи з властивістю експансії пов’язані з багатьма концепціями чистої математики, теорії обчислень та фізики. Крім того, експандери застосовуються в різних напрямках інформатики: теорії кодування, теорії мереж, теорії псевдовипадкових процесів і т. д. Наведено приклади сімейств (q + 1)-регулярних графів таких, що їх друге власне число не перевищує подвоєного кореня квадратного з q (родин геометричних графів Рамануджана). Зокрема, побудовано родину нових (q + 1)-регулярних графів Рамануджана обхвату 6 порядку 2(1+q+q2+q3), але вони не є ізоспектральними до геометрій простих груп типу Лі B2(q).
Завантаження
Посилання
Biggs N. L. Algebraic graph theory. Cambridge: Cambridge Univ. Press, 1993.
Horry S., Linial N., Wigderson A. Bull. (New Series) Amer. Math. Soc., 2006, 43, No 4: 439–561.
Alon N. Combinatorica, 1986, 6, No 3: 207–219. https://doi.org/10.1007/BF02579382
Polak M., Ustimenko V. A. On LPDC codes based on families of expanding graphs of increasing girths without edge-transitive automorphism group (to appear).
Buekenhout F. Handbook on incidence geometry. Amsterdam: North Holland, 1995.
Bourbaki N. Groupes et algebras de Lie: Chap. IV, V, VI. Paris: Hermann, 1968.
Ustimenko V. A. DAN USSR, 1987, 296, No 5: 1061–1065.
Ustimenko V. A. Ukr. Math. J., 1990, 40, No 3: 383–387.
Ustimenko V. A. On some properties of geometries of the Chevalley groups and their generalizations. In: Investigations in Algebraic Theory of Combinatorial Objects (Ed. I. A. Faradzev, A. A. Ivanov, M. H. Klin, A. J. Woldar), Dordrecht: Kluwer, 1991: 112–121 (Mathematics and Its Applications; Vol. 84).
Brower A. E., Cohen A. M., Niemaier A. Distance regular graphs, Berlin: Springer, 1989. https://doi.org/10.1007/978-3-642-74341-2
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2025 Доповіді Національної академії наук України
Ця робота ліцензується відповідно до Creative Commons Attribution-NonCommercial 4.0 International License.
