TY  - THES
A1  - Lee, Joon
T1  - Sparse random models in combinatorics
N2  - 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.
KW  - Random Graphs
KW  - Random CSP
KW  - Random Matrices
Y1  - 2023
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/72110
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30:3-721108
N1  - 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
CY  - Frankfurt am Main
ER  -