Sparse random and pseudorandom graphs and graph Ramsey theory
Final Report Abstract
The area of this project was extremal and probabilistic combinatorics with the focus on understanding of when certain, bounded in some sense, ubiquitous (in graph theory) structures appear in large sparse stuctures, and when structures become unavoidable even if one asks for such structure to be monochromatic after a large structure gets 2-colored (Ramsey theory). The prime objects of study were sparse random and pseudorandom graphs and their generalizations to hypergraphs. The project has led to thirteen scientific contributions. The results of the project include: a generalization of Riordan’s theorem about spanning structures in random graphs to random hypergraphs, the study of universal hypergraphs, an algorithmic result on tight Hamilton cycles in random hypergraphs. Furthermore, a development of general technique to address problems in randomly perturbed graphs was given. It was established that these graphs contain certain well-studied bounded degree spanning subgraphs (general bounded degree graphs, powers of Hamilton cycles, trees universally) usually ‘earlier’ than the corresponding random graphs. Also some applications of recently developed blow-up lemmas for sparse graphs have been studied, and a result of near-perfect triangle factors at the optimal density for so-called (n, d, λ)-graphs has been obtained. In Ramsey theory, the study of Ramsey properties of random hypergraphs identified a new type of threshold absent in the random graph case, and 1-statement (up to a logarithmic factor) of a conjecture of Kohayakawa and Kreuter has been proven. The study of minimal Ramsey hypergraphs was initiated and the results on vertex degrees and codegrees in minimal Ramsey 3-uniform hypergraphs have been given.
Publications
- “Minimum degrees and codegrees of Ramsey-minimal 3-uniform hypergraphs”, Combinatorics, Probability and Computing 25, 850–869, 2016
Dennis Clemens and Yury Person
(See online at https://doi.org/10.1016/j.endm.2015.06.005) - “On universal hypergraphs”, The Electronic Journal of Combinatorics 23 (4) (2016)
Samuel Hetterich, Olaf Parczyk and Yury Person
- “Spanning structures and universality in sparse hypergraphs”, Random Structures & Algorithms 49(4), 819–844, 2016
Olaf Parczyk and Yury Person
(See online at https://doi.org/10.1002/rsa.20690) - Embedding spanning bounded degree graphs in randomly perturbed graphs
Julia Böttcher, Richard Montgomery, Olaf Parczyk and Yury Person
- “Symmetric and asymmetric Ramsey properties in random hypergraphs”, Forum of Mathematics, Sigma, Vol. 5, e28, 47 pages, 2017
Luca Gugelmann, Rajko Nenadov, Yury Person, Nemanja Skorić, Angelika Steger and Henning Thomas
(See online at https://doi.org/10.1017/fms.2017.22) - Near-perfect clique-factors in sparse pseudo-random graphs
Jie Han, Yoshiharu Kohayakawa and Yury Person
