R. Nenadov

activity

20242026

collaborators

13 papers

math.CO2026

Smaller universal posets

Paul Bastide, Carla Groenland, Rajko Nenadov

We show that there is a constant $C > 0$ such that for each integer $n \geq 1$ , there is a poset on at most $2^{2 n /3 + C n}$ elements that contains each $n$ -element poset as an (i…

math.CO2026

Sumsets of random sets

Rajko Nenadov, Lander Verlinde

Given $m \in N$ and a $p$ -random subset $A \subseteq N$ , we asymptotically determine $lo g Pr (∣ N ∖ (A + A) ∣ \geq m)$ for $p$ above the threshold…

math.PR2026

The critical activation density in graph bootstrap percolation

Brett Kolesnik, Tamás Makai, TamÃ¡s Makai +6

In graph bootstrap percolation, edges of an Erdős-Rényi random graph $G_{n, p}$ are initially active, and activation spreads to other edges of $K_{n}$ via the combinatorics…

math.CO2026

Refuting Perfect Matchings in Spectral Expanders is Hard

Ari Biswas, Rajko Nenadov

This work studies the complexity of refuting the existence of a perfect matching in spectral expanders with an odd number of vertices, in the Polynomial Calculus (PC) and Sum of Sq…

math.CO2025

Improved bound on the number of cycle sets

Rajko Nenadov

The cycle set of a graph $G$ is the set consisting of all sizes of cycles in $G$ . Answering a conjecture of ErdÅs and Faudree, VerstraÃ«te showed that there are at most $2^{n - n^…

math.CO2025

Minors in small-set expanders

Michael Krivelevich, Rajko Nenadov

We study large minors in small-set expanders. More precisely, we consider graphs with $n$ vertices and the property that every set of size at most $I^\pm n / t$ expands by a factor of…