On new expanders of unbounded degree for practical applications in informatics
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 oth...
Gespeichert in:
| Veröffentlicht in: | Доповіді НАН України |
|---|---|
| Datum: | 2014 |
| ISSN: | 1025-6415 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Englisch |
| Veröffentlicht: |
Видавничий дім "Академперіодика" НАН України
2014
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/88632 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | On new expanders of unbounded degree for practical applications in informatics / M. Polak, V.A. Ustimenko // Доповiдi Нацiональної академiї наук України. — 2014. — № 12. — С. 44-50. — Бібліогр.: 10 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862746663970406400 |
|---|---|
| author | Polak, M. Ustimenko, V.A. |
| author_facet | Polak, M. Ustimenko, V.A. |
| citation_txt | On new expanders of unbounded degree for practical applications in informatics / M. Polak, V.A. Ustimenko // Доповiдi Нацiональної академiї наук України. — 2014. — № 12. — С. 44-50. — Бібліогр.: 10 назв. — англ. |
| collection | DSpace DC |
| container_title | Доповіді НАН України |
| description | 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).
|
| first_indexed | 2025-12-07T20:47:01Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-88632 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1025-6415 |
| language | English |
| last_indexed | 2025-12-07T20:47:01Z |
| publishDate | 2014 |
| publisher | Видавничий дім "Академперіодика" НАН України |
| record_format | dspace |
| spelling | Polak, M. Ustimenko, V.A. 2015-11-18T14:54:05Z 2015-11-18T14:54:05Z 2014 On new expanders of unbounded degree for practical applications in informatics / M. Polak, V.A. Ustimenko // Доповiдi Нацiональної академiї наук України. — 2014. — № 12. — С. 44-50. — Бібліогр.: 10 назв. — англ. 1025-6415 https://nasplib.isofts.kiev.ua/handle/123456789/88632 519.176, 519.157.2 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). The authors were the participants of the International Algebraic Conference dedicated to the 100-th
 anniversary of L.A. Kaluzhnin (July 7–12, 2014, Kyiv, Ukraine). Our paper is dedicated to the memory
 of Lev Kaluzhnin and his achievements in mathematics. en Видавничий дім "Академперіодика" НАН України Доповіді НАН України Інформатика та кібернетика On new expanders of unbounded degree for practical applications in informatics Про новi експандери необмеженого степеня для практичного застосування в iнформатицi О новых экспандерах неограниченной степени для практического применения в информатике Article published earlier |
| spellingShingle | On new expanders of unbounded degree for practical applications in informatics Polak, M. Ustimenko, V.A. Інформатика та кібернетика |
| title | On new expanders of unbounded degree for practical applications in informatics |
| title_alt | Про новi експандери необмеженого степеня для практичного застосування в iнформатицi О новых экспандерах неограниченной степени для практического применения в информатике |
| title_full | On new expanders of unbounded degree for practical applications in informatics |
| title_fullStr | On new expanders of unbounded degree for practical applications in informatics |
| title_full_unstemmed | On new expanders of unbounded degree for practical applications in informatics |
| title_short | On new expanders of unbounded degree for practical applications in informatics |
| title_sort | on new expanders of unbounded degree for practical applications in informatics |
| topic | Інформатика та кібернетика |
| topic_facet | Інформатика та кібернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/88632 |
| work_keys_str_mv | AT polakm onnewexpandersofunboundeddegreeforpracticalapplicationsininformatics AT ustimenkova onnewexpandersofunboundeddegreeforpracticalapplicationsininformatics AT polakm pronoviekspanderineobmeženogostepenâdlâpraktičnogozastosuvannâvinformatici AT ustimenkova pronoviekspanderineobmeženogostepenâdlâpraktičnogozastosuvannâvinformatici AT polakm onovyhékspanderahneograničennoistepenidlâpraktičeskogoprimeneniâvinformatike AT ustimenkova onovyhékspanderahneograničennoistepenidlâpraktičeskogoprimeneniâvinformatike |