Rend a rendezetlenségben – gráfelméleti példákkal

Order in the chaos with examples from graph theory

Authors

  • KÁSA Zoltán Sapientia

Keywords:

random structure, complete graph, Hamiltonian path, Hamiltonian cycle, De Bruijn graph , /, véletlenszerű struktúrák, teljes gráf, Hamilton-ú, Hamilton-kö, De Bruijn-gráf

Abstract

This is a kind of graph-theoretic essay, with new perspectives rather than new results, though there are too (e.q. theorems 2 and 4). In randomly created structures (be they natural or artificial) very often there exist ordered substructures. We will present here some of such structures in graph theory. 

Kivonat

Ez az írás egyféle gráfelméleti esszészerűség, inkább új szemlélettel, mint új eredményekkel, bár vannak ilyenek is (pl. 2. és 4. tétel). Azt vizsgáljuk, hogy egy struktúra, legyen az bármennyire is véletlenszerűen, rendezetlenül létrehozva, tartalmazhat-e valamilyen rendezett részstruktúrát.

References

Andrásfai Béla: Ismerkedés a gráfelmélettel, Tankönyvkiadó, Budapest, 1971.

Claude Berge: Théorie des graphes et ses applicatuions, Dunod, Paris, 1967. (románul: Teoria grafurilor și applicațiile ei, Editura Tehnică, București, 1969)

Johny Bond, Antal Iványi: Modelling of interconnection networks using De Bruijn graphs, in: Third Conference of Program Designer, Ed. A. Iványi, Budapest, 1987, pp. 75–87. https://tinyurl.com/2p8rzfmf

Zoltán Kása: On arc-disjoint Hamiltonian cycles in De Bruijn graphs, https://arxiv.org/abs/1003.1520

Zoltán Kása: On k-thin sets and their relation to generalized Ramsey number, Studia Universitatis Babes-Bolyai, Mathematica, 20 (1975) 54–59.

Kása Zoltán, Anisiu Mira-Cristiana: Szavak bonyolultsága, in: Iványi Antal (szerk.): Informatikai algoritmusok III., Budapest, mondAt Kiadó, 2013, pp. 1697–1739., ISBN 9789638759689 (angolul: https://www.researchgate.net/publication/274735246_Complexity_of_words )

Yaw-Ling Lin, Charles Ward, Bharat Jain, Steven Skiena: Constructing orthogonal de Bruijn sequences, in Algorithms and Data Structures, Lecture Notes in Computer Science, 2011, Volume 6844/2011, pp. 595–606.

M. H. Martin, A problem in arrangements, Bull. A.M.S. 40 (1934) 859–864.

Szemerédi-féle regularitási lemma, Wikipédia, https://hu.wikipedia.org/wiki/Szemerédi-féle_regularitási_lemma

Downloads

Published

2022-04-17

Issue

Section

Articles