Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
The phase transitions in directed acyclic graphs
Kassaye, M. T. 2025. The Phase Transitions in Directed Acyclic Graphs. Unpublished doctoral dissertation. Stellenbosch: Stellenbosch University [online]. Available: https://scholar.sun.ac.za/items/e00e14f4-4a03-4ed8-aaa2-c6270a476561
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Stellenbosch : Stellenbosch University
2025
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867614100191707136 |
|---|---|
| access_status_str | Open Access |
| author | Kassaye, Masreshaw Temere |
| author2 | Ralaivaosaona, Dimbinaina |
| author_browse | Kassaye, Masreshaw Temere Ralaivaosaona, Dimbinaina |
| author_facet | Ralaivaosaona, Dimbinaina Kassaye, Masreshaw Temere |
| author_sort | Kassaye, Masreshaw Temere |
| collection | Thesis |
| dc_rights_str_mv | Stellenbosch University |
| description | Kassaye, M. T. 2025. The Phase Transitions in Directed Acyclic
Graphs. Unpublished doctoral dissertation. Stellenbosch: Stellenbosch University [online]. Available: https://scholar.sun.ac.za/items/e00e14f4-4a03-4ed8-aaa2-c6270a476561 |
| format | Thesis |
| id | oai:scholar.sun.ac.za:10019.1/132570 |
| institution | Stellenbosch University (South Africa) |
| last_indexed | 2026-06-10T12:46:40.081Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from SUNScholar — Stellenbosch University Repository |
| publishDate | 2025 |
| publishDateRange | 2025 |
| publishDateSort | 2025 |
| publisher | Stellenbosch : Stellenbosch University |
| publisherStr | Stellenbosch : Stellenbosch University |
| record_format | dspace |
| source_str | SUNScholar — Stellenbosch University Repository |
| spelling | oai:scholar.sun.ac.za:10019.1/132570 The phase transitions in directed acyclic graphs Kassaye, Masreshaw Temere Ralaivaosaona, Dimbinaina Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences. Directed graphs Graph theory Phase transformations (Statistical physics) Random graphs UCTD Kassaye, M. T. 2025. The Phase Transitions in Directed Acyclic Graphs. Unpublished doctoral dissertation. Stellenbosch: Stellenbosch University [online]. Available: https://scholar.sun.ac.za/items/e00e14f4-4a03-4ed8-aaa2-c6270a476561 Thesis (PhD)--Stellenbosch University, 2025. ENGLISH ABSTRACT: Directed acyclic graphs (DAGs) are fundamental mathematical structures with numerous applications in both pure and applied science. They serve as the underlying structures for citation networks, food webs, Bayesian networks, and more. Despite their roles in modern science, DAGs have not received the same level of attention in mathematics as their undirected graph counterparts. In this thesis, we propose a model of a random labeled DAG defined on the vertex set [n] := {1, 2, 3, . . . , n} with a parameter p ∈ [0, 1]. This model, denoted by Dac(n, p), is derived from the standard binomial random digraph D(n, p), conditioned to be acyclic, i.e., with no directed cycles. The model is a natural generalization of the uniform random DAG model, which corresponds to the case where p = 1 2 . We are interested in the phase transitions that occur in Dac(n, p) in the sparse regime(i.e. the number of edges grows much slower than the maximum possible number of edges). To do so, we consider p of the form λ n , where λ ≥ 0 is fixed. Our study is divided into several parts. First, we study the number of occurrences of components with low excess as weak components of Dac(n, p). From this, we already observe that phase transitions occur at λ = 1 2 and at λ = 1. Then, we analyze the global structure of Dac(n, p) by determining the probability that Dac(n, p) belongs to a class of labeled DAGs consisting only of components with excess −1 or 0. Finally, we compare Dac(n, p) with other known graph models and deduce shared properties. Our method is analytic and is based on the analysis of generating functions for various classes of labeled DAGs and the saddle point method. AFRIKAANSE OPSOMMING: Gerigte asikliese grawe (DAGs) is fundamentele wiskundige strukture met talle toepassings in beide suiwer en toegepaste wetenskappe. Hulle dien as die onderliggende strukture vir aanhalingsnetwerke, voedselwebbe, Bayesiaanse netwerke, en meer. Ten spyte van hul rolle in moderne wetenskap, het DAGs nie dieselfde vlak van aandag in wiskunde ontvang as hul ongerigte graaf-eweknieë nie. In hierdie tesis stel ons ’n model voor van ’n ewekansige gemerkte DAG, gedefinieer op die kruinversameling [n] := {1, 2, 3, . . . , n}, met ’n parameter p ∈ [0, 1]. Hierdie model, aangedui deur Dac(n, p), is afgelei van die standaard binomiale ewekansige digraaf D(n, p), voorwaardelik dat dit asiklies is, d.w.s. sonder enige gerigte siklusse. Die model is ’n natuurlike veralgemening van die eenvormige ewekansige DAG-model, wat ooreenstem met die geval waar p = 1 2 . Ons ondersoek die fase-oorgange wat in Dac(n, p) in die skaars regime voorkom. Om dit te doen, beskou ons p van die vorm λ n , waar λ > 0 vasgestel is. Ons studie is verdeel in verskeie dele. Eerstens bestudeer ons die aantal voorkomste van komponente met laer oormaat as swak komponente van Dac(n, p). Hieruit sien ons reeds dat fase-oorgange voorkom by λ = 1 2 en by λ = 1. Daarna ontleed ons die globale struktuur van Dac(n, p) deur die waarskynlikheid te bepaal dat Dac(n, p) behoort aan ’n klas gemerkte DAGs wat slegs uit komponente met oormaat −1 of 0 bestaan. Ten slotte vergelyk ons Dac(n, p) met ander bekende graafmodelle om te sien of hulle soortgelyke eienskappe deel. Ons metode is analities en is gebaseer op die ontleding van genererende funksies vir verskeie klasse gemerkte DAGs en die saalpuntmetode. Doctoral 2025-06-11T09:09:39Z 2025-06-11T09:09:39Z 2025-03 Thesis https://scholar.sun.ac.za/handle/10019.1/132570 Stellenbosch University xii, 92 pages : illustrations application/pdf Stellenbosch : Stellenbosch University |
| spellingShingle | Directed graphs Graph theory Phase transformations (Statistical physics) Random graphs UCTD Kassaye, Masreshaw Temere The phase transitions in directed acyclic graphs |
| title | The phase transitions in directed acyclic graphs |
| title_full | The phase transitions in directed acyclic graphs |
| title_fullStr | The phase transitions in directed acyclic graphs |
| title_full_unstemmed | The phase transitions in directed acyclic graphs |
| title_short | The phase transitions in directed acyclic graphs |
| title_sort | phase transitions in directed acyclic graphs |
| topic | Directed graphs Graph theory Phase transformations (Statistical physics) Random graphs UCTD |
| url | https://scholar.sun.ac.za/handle/10019.1/132570 |
| work_keys_str_mv | AT kassayemasreshawtemere thephasetransitionsindirectedacyclicgraphs AT kassayemasreshawtemere phasetransitionsindirectedacyclicgraphs |