Sparse random models in combinatorics
- In this thesis, we cover two intimately related objects in combinatorics, namely random constraint satisfaction problems and random matrices. First we solve a classic constraint satisfaction problem, 2-SAT using the graph structure and a message passing algorithm called Belief Propagation. We also explore another message passing algorithm called Warning Propagation and prove a useful result that can be employed to analyze various type of random graphs. In particular, we use this Warning Propagation to study a Bernoulli sparse parity matrix and reveal a unique phase transition regarding replica symmetry. Lastly, we use variational methods and a version of local limit theorem to prove a sufficient condition for a general random matrix to be of full rank.
Download full text files
Additional Services
| Author: | Joon LeeGND |
|---|---|
| URN: | urn:nbn:de:hebis:30:3-721108 |
| DOI: | https://doi.org/10.21248/gups.72110 |
| Place of publication: | Frankfurt am Main |
| Referee: | Amin Coja-OghlanORCiDGND, Jane Pu Gao, Tobias WethORCiDGND, Jochen BlathGND |
| Advisor: | Amin Coja-Oghlan |
| Document Type: | Doctoral Thesis |
| Language: | English |
| Date of Publication (online): | 2023/02/21 |
| Year of first Publication: | 2022 |
| Publishing Institution: | Universitätsbibliothek Johann Christian Senckenberg |
| Granting Institution: | Johann Wolfgang Goethe-Universität |
| Date of final exam: | 2022/07/29 |
| Release Date: | 2023/02/24 |
| Tag: | Random CSP; Random Matrices Random Graphs |
| Page Number: | 223 |
| Note: | Kumulative Dissertation - enthält die eingereichten Manuskriptversionen (Author Submitted Manuscripts) der folgenden Artikel: Achlioptas, Dimitris; Coja-Oghlan, Amin; Hahn-Klimroth, Max; Lee, Joon; Müller, Noëla; Penschuck, Manuel; Zhou, Guangyan (2021): The number of satisfying assignments of random2-SAT formulas, 58(4), S. 609-647, ISSN 1098-2418. DOI: 10.1002/rsa.20993 Cooley, Oliver; Lee, Joon; Ravelomanana, Jean B. (2021): Warning Propagation: stability and subcriticality. arXiv:2111.15577. DOI: 10.48550/arXiv.2111.15577 Coja-Oghlan, Amin; Cooely, Oliver; Kang, Mihyun; Lee, Joon; Ravelomanana, Jean Bernoulli (2021): The sparse parity matrix. Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), S. 822-833 DOI: 10.1137/1.9781611977073.35 Coja-Oghlan, Amin; Gao, Pu; Hahn-Klimroth, Max; Lee, Joon; Müller, Noela Müller; Rolvien, Maurice (2021): The full rank condition for sparse random matrices. arXiv:2112.14090. DOI: 10.48550/arXiv.2112.14090 |
| HeBIS-PPN: | 50519290X |
| Institutes: | Informatik und Mathematik |
| Dewey Decimal Classification: | 5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik |
| Sammlungen: | Universitätspublikationen |
| Licence (German): |  Deutsches Urheberrecht |
