Rajko Nenadov

I am a Lecturer in Theoretical Computer Science at the University of Auckland, New Zealand.

I obtained PhD from ETH Zurich in 2016, under the supervision of Angelika Steger. I spent two years as a postdoc at the School of Mathematical Sciences at Monash University (Melbourne, Australia) hosted by Jane Gao and Nick Wormald, and another year and half back at ETH, where I was hosted by Benny Sudakov. The following four years I was a software engineer at Google Zurich, working mostly on Search Ranking algorithms. As of July 2023, I'm back in academia!

My research interests are broadly in combinatorics. Particularly, probabilistic methods, random structures, pseudorandomness, extremal graph theory, Ramsey theory, and applications to theoretical computer science

Publications

A. Biswas and R. Nenadov, Refuting perfect matchings in spectral expanders is hard [arXiv]
Submitted, 2025.

M. Krivelevich and R. Nenadov, Minors in small-set expanders [arXiv]
Submitted, 2025.

R. Nenadov, A remark on the independence number of sparse random Cayley sum graphs [arXiv]
Submitted, 2025.

R. Nenadov, Improved bound on the number of cycle sets [arXiv]
Submitted, 2025.

R. Nenadov, Hypergraph universality via branching random walks [arXiv]
Submitted, 2024.

R. Nenadov and L. Verlinde,
Containers with non-uniform co-degree conditions, and an application to nearly orthogonal sets [arXiv]
Submitted, 2024.

R. Nenadov and H. T. Pham, Spread blow-up lemma with an application to perturbed random graphs [arXiv]
Submitted, 2024.

J. Fox, R. Nenadov, and H. T. Pham, The largest subgraph without a forbidden induced subgraph [arXiv]
Submitted, 2024.

M. Christoph, R. Nenadov, and K. Petrova, The Hamilton space of pseudorandom graphs [arXiv]
Submitted, 2024.

R. Montgomery, R. Nenadov, J. Portier, and T. Szabó, Global rigidity of random graphs in R [arXiv]
Submitted, 2024.

N. Alon, N. Dodson, C. Jackson, R. McCarty, R. Nenadov, and L. Southern, Universality for graphs with bounded density [arXiv]
Submitted, 2024.

R. Nenadov, The number of arcs in Fq^2 of a given cardinality [arXiv]
Discrete & Computational Geometry, accepted, 2025.

R. Nenadov and H. T. Pham, Short proof of the hypergraph container theorem [arXiv, journal]
Combinatorics, Probability and Computing, accepted, 2025.

R. Nenadov, Counting sparse induced subgraphs in locally dense graphs [arXiv, journal]
European Journal of Combinatorics, 126:104125, 2025.

K. D. Barbosa, D. Mašulović, and R. Nenadov
A short note on the characterization of countable chains with finite big Ramsey spectra [arXiv, journal]
Order, 41:573-577, 2024.

N. Draganić and R. Nenadov, Edge-disjoint paths in expanders: online with removals [arXiv]
Proc. of the ACM-SIAM SODA 2024, 4554-4563

R. Nenadov, Probabilistic hypergraph containers [journal, arXiv]
Israel Journal of Mathematics, 261:879-897, 2024.

D. Conlon, R. Nenadov, and M. Trujić, On the size-Ramsey number of grids [arXiv, journal]
Combinatorics, Probability and Computing, 32(6):874-880, 2023.

R. Nenadov, Routing permutations on spectral expanders via matchings [arXiv, journal]
Combinatorica, 43:737-742, 2023.

R. Nenadov, Probabilistic intuition holds for a class of small subgraph games [arXiv, journal]
Proceedings of the American Mathematical Society, 151:1495-1501, 2023.

R. Nenadov, A new proof of the KŁR conjecture [arXiv, journal]
Advances in Mathematics, 406:108518, 2022.
Companion note: Small subsets without k-term arithmetic progressions [arXiv]

D. Conlon, R. Nenadov, and M. Trujić, The size-Ramsey number of cubic graphs [arXiv, journal]
Bulletin of the London Mathematical Society, 54(6):2135-2150, 2022.

N. Draganić, M. Krivelevich, and R. Nenadov
Rolling backwards can move you forward: on embedding problems in sparse expanders [arXiv, journal]
Transactions of the American Mathematical Society, 375:5195-5216, 2022.
Proc. of the ACM-SIAM SODA 2021, 123–134.

A. Liebenau and R. Nenadov, The threshold bias of the clique-factor game [arXiv, journal]
Journal of Combinatorial Theory, Series B, 152:221-247, 2022.

N. Draganić, M. Krivelevich, and R. Nenadov, The size-Ramsey number of short subdivisions [arXiv, journal]
Random Structures & Algorithms, 59(1):68-78, 2021.

M. Krivelevich and R. Nenadov, Complete minors in graphs without sparse cuts [arXiv, journal]
International Mathematics Research Notices (IMRN), 2021(12): 8996–9015, 2021.

R. Nenadov and M. Trujić, Sprinkling a few random edges doubles the power [arXiv, journal]
SIAM Journal on Discrete Mathematics, 35(2):988–1004, 2021.

R. Nenadov, A. Steger, and P. Su, An O(N) time algorithm for finding Hamilton cycles with high probability [arxiv, proc]
12th Innovations in Theoretical Computer Science Conference ITCS 2021, vol 185, 60:1-60:17, 2021.

R. Nenadov, B. Sudakov, and A. Z. Wagner, Completion and deficiency problems [arXiv, journal]
Journal of Combinatorial Theory, Series B, 145:214–240, 2020.

R. Nenadov, B. Sudakov, and M. Tyomkyn, Proof of the Brown–Erdős–Sós conjecture in groups [arXiv, journal]
Mathematical Proceedings of the Cambridge Philosophical Society, 169(2):323–333, 2020.

R. Nenadov, M. Sawhney, B. Sudakov, and A. Z. Wagner, Bounded degree spanners of the hypercube [arXiv, journal]
The Electronic Journal of Combinatorics, 27(3), 2020.

F. Mousset, R. Nenadov, and W. Samotij, Towards the Kohayakawa–Kreuter conjecture on asymmetric Ramsey properties [arXiv, journal]
Combinatorics, Probability and Computing, 29(6):943–955, 2020.

R. Nenadov and Y. Pehova, On a Ramsey–Turán variant of the Hajnal–Szemerédi theorem [arXiv, journal]
SIAM Journal on Discrete Mathematics, 34(2):1001–1010, 2020.

R. Nenadov and N. Škorić, On Komlós’ tiling theorem in random graphs [arXiv, journal]
Combinatorics, Probability and Computing, 29(1):113–127, 2020.

R. Nenadov, Triangle-factors in pseudorandom graphs [arXiv, journal]
Bulletin of the London Mathematical Society, 51(3):421–430, 2019.

R. Nenadov, A. Steger, and M. Trujić, Resilience of perfect matchings and hamiltonicity in random graph processes [arXiv, journal]
Random Structures & Algorithms, 54(4):797–819, 2019.

N. Alon and R. Nenadov, Optimal induced universal graphs for bounded-degree graphs [arXiv, journal]
Mathematical Proceedings of the Cambridge Philosophical Society, 166(1):61–74, 2019.
Proc. of the ACM-SIAM SODA 2017, 1149–1157.

R. Nenadov and N. Škorić, Powers of hamilton cycles in random graphs and tight hamilton cycles in random hypergraphs [arXiv, journal]
Random Structures & Algorithms, 54(1):187–208, 2018.

A. Ferber and R. Nenadov, Spanning universality in random graphs [arXiv, journal]
Random Structures & Algorithms, 53(4):604–637, 2018.

D. Korándi, F. Mousset, R. Nenadov, N. Škorić, and B. Sudakov, Monochromatic cycle covers in random graphs [arXiv, journal]
Random Structures & Algorithms, 53(4):667–691, 2018.

R. Nenadov, Star-factors in graphs with large minimum degree [arXiv, journal]
Journal of Combinatorial Theory, Series B, 133:78–87, 2018.

L. Gugelmann, R. Nenadov, Y. Person, N. Škorić, A. Steger, and H. Thomas
Symmetric and asymmetric Ramsey properties in random hypergraphs [arXiv, journal]
Forum of Mathematics, Sigma, 5:e28, 2017.

A. Ferber, R. Nenadov, A. Noever, U. Peter, and N. Škorić, Robust hamiltonicity of random directed graphs [arXiv, journal]
Journal of Combinatorial Theory, Series B, 126:1–23, 2017.
Proc. of the ACM-SIAM SODA 2015, 1752–1758.

R. Nenadov, P. Pfister, and A. Steger, Unique reconstruction threshold for random jigsaw puzzles [arXiv, journal]
Chicago Journal of Theoretical Computer Science, 2017:2, June 2017.

D. Conlon, A. Ferber, R. Nenadov, and N. Škorić, Almost-spanning universality in random graphs [arXiv, journal]
Random Structures & Algorithms, 50(3):380–393, 2017.

R. Nenadov, Y. Person, N. Škorić, and A. Steger
An algorithmic framework for obtaining lower bounds for random Ramsey problems [arXiv, journal]
Journal of Combinatorial Theory, Series B, 124:1–38, 2017.
Proc. of the ACM-SIAM SODA 2015, 1743–1751.

R. Nenadov, A. Steger, and M. Stojaković, On the threshold for the Maker-Breaker H-game [arXiv, journal]
Random Structures & Algorithms, 49(3):558–578, 2016.

A. Ferber, R. Nenadov, and U. Peter, Universality of random graphs and rainbow embedding [arXiv, journal]
Random Structures & Algorithms, 48(3):546–564, 2016.

R. Nenadov and A. Steger, A short proof of the random Ramsey theorem [pdf, journal]
Combinatorics, Probability and Computing, 25(01):130–144, 2016.

F. Mousset, R. Nenadov, and A. Steger, On the number of graphs without large cliques [arXiv, journal]
SIAM Journal on Discrete Mathematics, 28(4):1980–1986, 2014.

D. Mašulović, R. Nenadov, and N. Škorić, On finite reflexive homomorphism-homogeneous binary relational systems [arXiv, journal]
Discrete Mathematics, 311:2543–2555, 2011.