On new expanders of unbounded degree for practical applications in informatics

Abstract

A method of construction of new examples of families of expander graphs of unbounded degree is presented. The property of being an expander seems significant in many of these mathematical, computational, and physical contexts. Even more, expanders are surprisingly applicable in other computational aspects: in the theory of error correcting codes, computer networking theory, the theory of pseudorandomness, etc. We present the new families of (q + 1)-regular graphs with the second largest eigenvalue of at most 2√q for every prime power q (geometrical Ramanujan graphs). In particular, we construct a family of new (q+1)-regular Ramanujan graphs of girth 6 of order 2(1+q+q²+q³). They are not isospectric to the geometry of the simple Lie group B₂(q).

Розглянуто метод побудови нових прикладiв родин графiв-експандерiв необмеженого степеня. Графи з властивiстю експансiї пов’язанi з багатьма концепцiями чистої математики, теорiї обчислень та фiзики. Крiм того, експандери застосовуються в рiзних напрямках iнформатики: теорiї кодування, теорiї мереж, теорiї псевдовипадкових процесiв i т. д. Наведено приклади сiмейств (q + 1)-регулярних графiв таких, що їх друге власне число не перевищує подвоєного кореня квадратного з q (родин геометричних графiв Рамануджана). Зокрема, побудовано родину нових (q+1)-регулярних графiв Рамануджана обхвату 6 порядку 2(1+q+q²+q³), але вони не є iзоспектральними до геометрiй простих груп типу Лi B₂(q).

Представлен метод построения новых примеров семейств графов-экспандеров неограниченной степени. Графы со свойством экспансии связаны с многими концепциями в чистой математике, теории вычислений и физики. Кроме того, экспандеры применяются в различных направлениях информатики: теории кодирования, теории сетей, теории псевдослучайных процессов и т. д. Приведены примеры семейств (q +1)-регулярных графов с вторым собственным значением, не превышаюшим удвоенного корня квадратного из q (семейств геометрических графов Рамануджана). В частности, построено семейство новых (q+1)-регулярных графов Рамануджана обхвата 6 порядка 2(1+q+q²+q³), но они не изоспектральны геометриям простых групп типа Ли B₂(q).