# Olaf Parczyk

Freie Universität Berlin
Department of Mathematics and Computer Science
Arnimallee 3
14195 Berlin
Germany
parczyk@mi.fu-berlin.de

I am a Math+ Postdoc in the Combinatorics and Graph Theory Group of Tibor Szabó at FU-Berlin and associated with the Interactive Optimization and Learning Laboratory of Sebastian Pokutta at the Zuse Institute Berlin. Previously, I was a visiting fellow at the London School of Economics and Political Science funded by a fellowship of the German Research Foundation (DFG, Grant PA 3513/1-1) and a postdoctoral researcher at TU Ilmenau. I obtained my Ph.D. at Goethe University Frankfurt am Main, where my supervisor was Yury Person.

### Research Interests

My research interests are probabilistic and extremal combinatorics, Ramsey theory, and machine learning. I am mostly working on embedding type problems for graphs and usually they involve randomness in one way or the other.

### Recent Contributions

• We prove that random hypergraphs are asymptotically almost surely resiliently Hamiltonian. More precisely, for any $$\gamma>0$$ and $$k\ge3$$, we show that asymptotically almost surely, every subgraph of the binomial random $$k$$-uniform hypergraph $$G^{(k)}\big(n,n^{\gamma-1}\big)$$ in which all $$(k-1)$$-sets are contained in at least $$(1/2+\gamma)pn$$ edges has a tight Hamilton cycle. This is a cyclic ordering of the $$n$$ vertices such that each consecutive $$k$$ vertices forms an edge.
This is joint work with Peter Allen and Vincent Pfenninger, arXiv:2105.04513.
• We study the problem of finding pairwise vertex-disjoint triangles in the randomly perturbed graph model, which is the union of any n-vertex graph $$G$$ with linear minimum degree and the binomial random graph $$G(n,p)$$. We prove that asymptotically almost surely $$G \cup G(n,p)$$ contains $$\min\{\delta(G), \lceil n/3 \rceil \}$$ pairwise vertex-disjoint triangles, provided that $$p \ge C\, \log n/n$$, where $$C$$ is a large enough constant. This resolves the last open case for the existence of triangle-factors in randomly perturbed graphs.
This is joint work with Julia Böttcher, Amedeo Sgueglia, and Jozef Skokan, arXiv:2011.07612.

## Publications

### Preprints

• Resilience for tight Hamiltonicity with Peter Allen and Vincent Pfenninger. arXiv:2105.04513.
• Triangles in randomly perturbed graphs with Julia Böttcher, Amedeo Sgueglia, and Jozef Skokan. arXiv:2011.07612.
• Near optimal sparsity-constrained group testing: improved bounds with Oliver Gebhard, Max Hahn-Klimroth, Manuel Penschuck, Maurice Rolvien, Jonathan Scarlett, and Nelvin Tan. arXiv:2004.11860.
• Anti-Ramsey threshold of complete graphs for sparse graphs with Yoshiharu Kohayakawa, Guilherme O. Mota, and Jakob Schnitzer. arXiv:1902.00306.

### To appear

• Positional games on randomly perturbed graphs with Dennis Clemens, Fabian Hamann, and Yannick Mogge, to appear in SIAM Journal on Discrete Mathematics. arXiv:2009.14583.
• Anti-Ramsey threshold of cycles with Garbiel F. Barros, Bruno P. Cavalar, and Guilherme O. Mota, to appear in Discrete Applied Mathematics. arXiv:2006.02079.

### Published

1. The size-Ramsey number of 3-uniform tight paths with Jie Han, Yoshiharu Kohayakawa, Shoham Letzter, and Guilherme O. Mota, Advances in Combinatorics, 2021:5, 12pp. DOI, arXiv.
2. Random perturbation of sparse graphs with Max Hahn-Klimroth, Giulia S. Maesaka, Yannick Mogge, and Samuel Mohr, The Electronic Journal of Combinatorics (2021), no 2, P2.26. DOI, arXiv.
3. The size-Ramsey number of powers of bounded degree trees with Sören Berger, Yoshiharu Kohayakawa, Giulia S. Maesaka, Taísa Martins, Walner Mendonça, and Guilherme O. Mota. Journal of the London Mathematical Society 103 (2021), no 4, 1314–1332. DOI, arXiv.
4. Finding tight Hamilton cycles in random hypergraphs faster with Peter Allen, Christoph Koch, and Yury Person. Combinatorics, Probability and Computing 30 (2021), no 2, 239–257. DOI, arXiv.
5. Embedding spanning bounded degree graphs in randomly perturbed graphs with Julia Böttcher, Richard Montgomery, and Yury Person. Mathematika 66 (2020), no 2, 422–447. DOI, arXiv.
6. 2-universality in randomly perturbed graphs. European Journal of Combinatorics 87 (2020), 103–118. DOI, arXiv.
7. Semi-random graph process with Omri Ben Eliezer, Dan Hefetz, Gal Kronenberg, Clara Shikelman, and Miloš Stojaković. Random Structures & Algorithms 56 (2020), no 3, 648–675. DOI, arXiv.
8. Universality of bounded degree spanning trees in randomly perturbed graphs with Julia Böttcher, Jie Han, Yoshiharu Kohayakawa, Richard Montgomery, and Yury Person. Random Structures & Algorithms 55 (2019), no 4, 854–864. DOI, arXiv.
9. Spanning structures and universality in sparse hypergraphs with Yury Person. Random Structures & Algorithms 49 (2016), no 4, 819–844. DOI, arXiv.
10. On universal hypergraphs with Samuel Hetterich and Yury Person. The Electronic Journal of Combinatorics (2016), no 4, P4.28. DOI, arXiv.

### Conference Proceedings

• The square of a Hamilton cycle in randomly perturbed graphs with Julia Böttcher, Amedeo Sgueglia, and Jozef Skokan, EUROCOMB 2021
• Waiter-Client Games on Randomly Perturbed Graphs with Dennis Clemens, Fabian Hamann, and Yannick Mogge, EUROCOMB 2021.
• Cycle factors in randomly perturbed graphs with Julia Böttcher, Amedeo Sgueglia, and Jozef Skokan, LAGOS 2021
• The size-Ramsey number of powers of bounded degree trees with Sören Berger, Yoshiharu Kohayakawa, Giulia S. Maesaka, Taísa Martins, Walner Mendonça, and Guilherme O. Mota. Acta Mathematica Universitatis Comenianae 88 (2019), no 3, 451–456. URL.
• More non-bipartite forcing pairs with Tamas Hubai, Dan Král, and Yury Person. Acta Mathematica Universitatis Comenianae 88 (2019), no 3, 819–825. URL, arXiv.
• Almost spanning universality in random graphs. Acta Mathematica Universitatis Comenianae 88 (2019), no 3, 997–1002. URL.
• Anti-Ramsey threshold of cycles for sparse graphs with Gabriel F. Barros, Bruno P. Cavalar, and Guilherme O. Mota. Electronic Notes in Theoretical Computer Science 346 (2019), 89–98. DOI, arXiv.
• Finding tight Hamilton cycles in random hypergraphs faster with Peter Allen, Christoph Koch, and Yury Person. LATIN 2018: Theoretical Informatics. LATIN 2018. Lecture Notes in Computer Science, vol 10807. Springer, Cham. DOI.
• Embedding spanning bounded degree subgraphs in randomly perturbed graphs with Julia Böttcher, Richard Montgomery, and Yury Person. Electronic Notes in Discrete Mathematics 61 (2017), 155–161. DOI.
• On spanning structures in random hypergraphs with Yury Person. Electronic Notes in Discrete Mathematics 49 (2015), 611–619. DOI.

## Theses

• Doctoral thesis: Spanning structures in random graphs and hypergraphs, Goethe Universität Frankfurt am Main, 2017.
• Master’s thesis: On Sidorenko’s conjecture, Freie Universität Berlin, 2014.
• Bachelor’s thesis: Kombinatorischer Nullstellensatz, Freie Universität Berlin, 2013.

Created with Pandoc. Last update August 2021.