On new results on extremal graph theory, theory of algebraic graphs, and their applications

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 fam...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Veröffentlicht in:	Доповіді НАН України
Datum:	2022
1. Verfasser:	Ustimenko, V.O.
Format:	Artikel
Sprache:	English
Veröffentlicht:	Видавничий дім "Академперіодика" НАН України 2022
Schlagworte:	Інформатика та кібернетика
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/187171
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 results on extremal graph theory, theory of algebraic graphs, and their applications / V.O. Ustimenko // Доповіді Національної академії наук України. — 2022. — № 4. — С. 25-32. — Бібліогр.: 15 назв. — англ.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-187171
record_format	dspace
spelling	Ustimenko, V.O. 2022-12-08T19:13:36Z 2022-12-08T19:13:36Z 2022 On new results on extremal graph theory, theory of algebraic graphs, and their applications / V.O. Ustimenko // Доповіді Національної академії наук України. — 2022. — № 4. — С. 25-32. — Бібліогр.: 15 назв. — англ. 1025-6415 DOI: doi.org/10.15407/dopovidi2022.04.025 https://nasplib.isofts.kiev.ua/handle/123456789/187171 519.176, 519.157.2 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сом. The content of the paper was present as a talk at the international conference at the end of the year of 2021 in Kyiv. The talk was dedicated to the memory of V. V. Sergeichuk (1949-2021), who was a prominent member of the algebraic community of Ukraine. This research is supported by Fellowship of British Academy for Researchers at Risk. en Видавничий дім "Академперіодика" НАН України Доповіді НАН України Інформатика та кібернетика On new results on extremal graph theory, theory of algebraic graphs, and their applications Про нові результати екстремальної теорії графiв, теорії алгебраїчних графів та їх застосування Article published earlier
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	On new results on extremal graph theory, theory of algebraic graphs, and their applications
spellingShingle	On new results on extremal graph theory, theory of algebraic graphs, and their applications Ustimenko, V.O. Інформатика та кібернетика
title_short	On new results on extremal graph theory, theory of algebraic graphs, and their applications
title_full	On new results on extremal graph theory, theory of algebraic graphs, and their applications
title_fullStr	On new results on extremal graph theory, theory of algebraic graphs, and their applications
title_full_unstemmed	On new results on extremal graph theory, theory of algebraic graphs, and their applications
title_sort	on new results on extremal graph theory, theory of algebraic graphs, and their applications
author	Ustimenko, V.O.
author_facet	Ustimenko, V.O.
topic	Інформатика та кібернетика
topic_facet	Інформатика та кібернетика
publishDate	2022
language	English
container_title	Доповіді НАН України
publisher	Видавничий дім "Академперіодика" НАН України
format	Article
title_alt	Про нові результати екстремальної теорії графiв, теорії алгебраїчних графів та їх застосування
description	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сом.
issn	1025-6415
url	https://nasplib.isofts.kiev.ua/handle/123456789/187171
citation_txt	On new results on extremal graph theory, theory of algebraic graphs, and their applications / V.O. Ustimenko // Доповіді Національної академії наук України. — 2022. — № 4. — С. 25-32. — Бібліогр.: 15 назв. — англ.
work_keys_str_mv	AT ustimenkovo onnewresultsonextremalgraphtheorytheoryofalgebraicgraphsandtheirapplications AT ustimenkovo pronovírezulʹtatiekstremalʹnoíteoríígrafivteorííalgebraíčnihgrafívtaíhzastosuvannâ
first_indexed	2025-11-29T11:02:02Z
last_indexed	2025-11-29T11:02:02Z
_version_	1850854820244619264

On new results on extremal graph theory, theory of algebraic graphs, and their applications

Institution

Ähnliche Einträge