On new results on extremal graph theory, theory of algebraic graphs, and their applications
Завантаження...
Дата
Автори
Назва журналу
Номер ISSN
Назва тому
Видавець
Видавничий дім "Академперіодика" НАН України
Анотація
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 Kⁿ,
n > 1, and cycle indicator ≥ 2n + 2 such that their projective limit is well defined and isomorphic to an infinite forest.
Описано нові конструктивні приклади нескінченних сімейств графів малого світу та великого обхвату. Коротко оглянуто застосування цих об’єктів для побудови LDPC кодів та криптографічних алгоритмів. Визначено сімейства однорідних алгебраїчних графів великого обхвату над довільним комутативним кільцем К. Для кожного комутативного кільця цілісності K, |K| > 2, наведено сімейство дводольних однорідних алгебраїчних графів великого обхвату над К, утворене графами з многовидами точок і прямих, ізоморфними Kⁿ, та цикловим показником ≥ 2n + 2. З цим сімейством пов’язано проєктивну границю графів, що є нескінченним лiсом.
Описано нові конструктивні приклади нескінченних сімейств графів малого світу та великого обхвату. Коротко оглянуто застосування цих об’єктів для побудови LDPC кодів та криптографічних алгоритмів. Визначено сімейства однорідних алгебраїчних графів великого обхвату над довільним комутативним кільцем К. Для кожного комутативного кільця цілісності K, |K| > 2, наведено сімейство дводольних однорідних алгебраїчних графів великого обхвату над К, утворене графами з многовидами точок і прямих, ізоморфними Kⁿ, та цикловим показником ≥ 2n + 2. З цим сімейством пов’язано проєктивну границю графів, що є нескінченним лiсом.
Опис
Теми
Інформатика та кібернетика
Цитування
On new results on extremal graph theory, theory of algebraic graphs, and their applications / V.O. Ustimenko // Доповіді Національної академії наук України. — 2022. — № 4. — С. 25-32. — Бібліогр.: 15 назв. — англ.