Rend a rendezetlenségben – gráfelméleti példákkal
Order in the chaos with examples from graph theory
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áfAbstract
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
