PTRCSP - Phase Transitions in Random Constraint Satisfaction Problems
Summary and Main Objectives
The systematic investigation of random discrete structures and processes was initiated by Erdös and Renyi in a seminal paper about random graphs in 1960. Since then the study of such objects has become an important topic that has remarkable applications not only in combinatorics, but also in computer science and statistical physics.Random discrete objects have two striking characteristics. First, they often exhibit phase transitions, meaning that only small changes in some typically local control parameter result in dramatic changes of the global structure. Second, several statistics of the models concentrate, that is, although the support of the underlying distribution is large, the random variables usually take values in a small set only. A central topic is the investigation of the fine behaviour, namely the determination of the limiting distribution.
Although the current knowledge about random discrete structures is broad, there are many fundamental and long-standing questions with respect to the two key characteristics. In particular, up to a small number of notable exceptions, several well-studied models undoubtedly exhibit phase transitions, but we are not able to understand them from a mathematical viewpoint nor to investigate their fine properties. The goal of the proposed project is to study some prominent open problems whose solution will improve significantly our general understanding of phase transitions and of the fine behaviour in random discrete structures. The objectives include the establishment of phase transitions in random constraint satisfaction problems and the analysis of the limiting distribution of central parameters, like the chromatic number in dense random graphs. All these problems are known to be difficult and fundamental, and the results of this project will open up new avenues for the study of random discrete objects, both sparse and dense.
Project term: 2018-2023
Funded by: ERC, Consolidator Grant
(Former) Team Members
Publications and Preprints
Coloring random graphs: tame colourings (A. Heckel and K. Panagiotou)Preprint: arXiv:2306.07253, submitted for publication, 2023.
A simple path to component sizes in critical random graphs
(U. de Ambroggio)
Preprint: arXiv:2201.01142, accepted in SIAM Journal on Discrte Mathematics, 2023.
Weighted Online Search (S. Angelopoulos, K. Panagiotou)
Journal of Computer and Systems Sciences, 138, 103457, 2023.
Exact-Size Sampling of Enriched Trees in Linear Time (K. Panagiotou, L. Ramzews and B. Stufler)
SIAM Journal on Computing, 52(5), p. 1097-1131, 2023.
Dispersion on the Complete Graph (U. de Ambroggio, T. Makai, K. Panagiotou)
European Conference on Combinatorics, Graph Theory and Applications (EuroComb '23), p. 336-342, 2023.
The hitting time of clique factors (A. Heckel, M. Kaufmann, N. Müller, M. Pasch)
European Conference on Combinatorics, Graph Theory and Applications (EuroComb '23), p. 552-560, 2023.
Cluster Statistics in Expansive Combinatorial Structures (K. Panagiotou and L. Ramzews)
Preprint: arXiv:2208.00925, submitted for publication, 2022.
How does the chromatic number of a random graph vary? (A. Heckel, O. Riordan)
Journal of the London Mathematical Society, 108(5), p. 1769-1815, 2023.
Mutual Information, Information-Theoretic Thresholds and the Condensation Phenomenon at Positive Temperature (K. Panagiotou and M. Pasch)
Preprint: arXiv:2207.11002, submitted for publication, 2022.
Belief Propagation on the random k-SAT model (A. Coja-Oghlan, N. Müller, J. B. Ravelomanana)
Annals of Applied Probability, 32(5), p. 3718-3796, 2022.
Inference and mutual information on random factor graphs
(A. Coja-Oghlan, M. Hahn-Klimroth, P. Loick, N. Müller, K. Panagiotou, M. Pasch)
38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021), Article No. 24, 2021.
Non-concentration of the chromatic number of a random graph (A. Heckel)
Journal of the American Mathematical Society, 34, p. 245-260, 2021.
The Chromatic Number of Dense Random Block Graphs (A. Martinsson, K. Panagiotou, P. Su, M. Trujic)
Preprint: arXiv:2007.07700, submitted for publication.
On the Probability of Nonexistence in Binomial Subsets (F. Mousset, A. Noever K. Panagiotou and W. Samotij)
Annals of Probability, 48(1), p. 493-525, 2020.
Managing Default Contagion in Inhomogeneous Financial Networks (N. Detering, T. Meyer-Brandis, K. Panagiotou, and D. Ritter)
SIAM Journal of Financial Mathematics, 10(2), p. 578-614, 2019.
Satisfiability Thresholds for Regular Occupation Problems (K. Panagiotou, M. Pasch)
Proceedings of the 46th International Colloquium on Automata, Languages and Programming (ICALP '19), Article No. 90, 2019.
Load Thresholds for Cuckoo Hashing with Double Hashing (M. Mitzenmacher, K. Panagiotou and S. Walzer)
Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT '18), Article No. 29, 2018.