R. Nenadov

activity

20092026

most citedOn the number of graphs without large cliques

14 citations · 52 across the 41 of their papers we have counts for

collaborators

57 papers

math.CO2026

Probabilistic and game thresholds

Rajko Nenadov

Let $X$ be a finite set and $F \subseteq 2^{X}$ a non-trivial increasing property. We show that the bias-threshold $b (F)$ for the Picker-Chooser $F$ -gam…

math.CO2026

Poset dimension and maximum comparability degree

Carla Groenland, Richard Montgomery, Rajko Nenadov +1

In 1986, Füredi and Kahn showed that the dimension $dim (P)$ of any finite poset $P$ satisfies $dim (P) = O (d lo g^{2} d)$ , where $d$ is the maximum degree of the comparability graph…

math.CO2026

The typical structure of sets with large sumset

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, Rajko Nenadov +3

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.CO2025

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.CO2025

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

A remark on the independence number of sparse random Cayley sum graphs

Rajko Nenadov

The Cayley sum graph $Γ_{S}$ of a set $S \subseteq Z_{n}$ is defined on the vertex set $Z_{n}$ , with an edge between distinct $x, y \in Z_{n}$ if $x + y \in S$ .…

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 $α n / t$ expands by a factor of $…

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^{1…

math.CO2024

Hypergraph universality via branching random walks

Rajko Nenadov

Given a family of hypergraphs $H$ , we say that a hypergraph $Γ$ is $H$ -universal if it contains every $H \in H$ as a subgraph. For $D, r \in \mathbb{N…

math.CO2024

Multipartite nearly orthogonal sets over finite fields

Rajko Nenadov, Lander Verlinde

For a field $F$ and integers $d, k$ and $ℓ$ , a set $A \subseteq F^{d}$ is called $(k, ℓ)$ -nearly orthogonal if all vectors in $A$ are non-self-orthogonal and e…

math.CO2024

The number of arcs in $F_{q}^{2}$ of a given cardinality

Rajko Nenadov

A subset of $F_{q}^{2}$ is called an arc if it does not contain three collinear points. We show that there are at most $(m ( 1 + o ( 1 )) q)$ arcs of size $m \gg q^{1/2} (\l…

math.CO2024

Counting sparse induced subgraphs in locally dense graphs

Rajko Nenadov

An $n$ -vertex graph $G$ is locally dense if every induced subgraph of size larger than $ζ n$ has density at least $d > 0$ , for some parameters $ζ, d > 0$ . We show that the number of…

math.CO2024

Spread blow-up lemma with an application to perturbed random graphs

Rajko Nenadov, Huy Tuan Pham

Combining ideas of Pham, Sah, Sawhney, and Simkin on spread perfect matchings in super-regular bipartite graphs with an algorithmic blow-up lemma, we prove a spread version of the…

math.CO2024

Short proof of the hypergraph container theorem

Rajko Nenadov, Huy Tuan Pham

We present a short and simple proof of the celebrated hypergraph container theorem of Balogh--Morris--Samotij and Saxton--Thomason. On a high level, our argument utilises the idea…

math.CO2024

The largest subgraph without a forbidden induced subgraph

Jacob Fox, Rajko Nenadov, Huy Tuan Pham

We initiate the systematic study of the following Turán-type question. Suppose $Γ$ is a graph with $n$ vertices such that the edge density between any pair of subsets of vertices o…

math.CO2024

The Hamilton space of pseudorandom graphs

Micha Christoph, Rajko Nenadov, Kalina Petrova

We show that if $n$ is odd and $p \geq C lo g n / n$ , then with high probability Hamilton cycles in $G (n, p)$ span its cycle space. More generally, we show this holds for a class of…

math.CO2024

Global rigidity of random graphs in $R$

Richard Montgomery, Rajko Nenadov, Julien Portier +1

We investigate the problem of reconstructing a set $P \subseteq R$ of distinct points, where the only information available about $P$ consists of the distances between some…

math.CO2023

Universality for graphs with bounded density

Noga Alon, Natalie Dodson, Carmen Jackson +3

A graph $G$ is $universal$ for a (finite) family $H$ of graphs if every $H \in H$ is a subgraph of $G$ . For a given family $H$ , the goal is t…

cs.DS2023

Edge-disjoint paths in expanders: online with removals

Nemanja Draganić, Rajko Nenadov

We consider the problem of finding edge-disjoint paths between given pairs of vertices in a sufficiently strong $d$ -regular expander graph $G$ with $n$ vertices. In particular, we…

math.LO2023

A short note on the characterization of countable chains with finite big Ramsey spectra

Keegan Dasilva Barbosa, Dragan Mašulović, Rajko Nenadov

In this short note we confirm the deep structural correspondence between the complexity of a countable scattered chain (= strict linear order) and its big Ramsey combinatorics: we…

math.CO2022

Routing permutations on spectral expanders via matchings

Rajko Nenadov

We consider the following matching-based routing problem. Initially, each vertex $v$ of a connected graph $G$ is occupied by a pebble which has a unique destination $π (v)$ . In each…

math.CO2022

Probabilistic intuition holds for a class of small subgraph games

Rajko Nenadov

Consider the following two-player game on the edges of $K_{n}$ , the complete graph with $n$ vertices: Starting with an empty graph $G$ on the vertex set of $K_{n}$ , in each round the f…

math.CO2022

On the size-Ramsey number of grids

David Conlon, Rajko Nenadov, Miloš Trujić

We show that the size-Ramsey number of the $n \times n$ grid graph is $O (n^{5/4})$ , improving a previous bound of $n^{3/2 + o (1)}$ by Clemens, Miralaei, Reding, Schac…

Probabilistic and game thresholds

Poset dimension and maximum comparability degree

The typical structure of sets with large sumset

The critical activation density in graph bootstrap percolation

Smaller universal posets

Refuting Perfect Matchings in Spectral Expanders is Hard

A remark on the independence number of sparse random Cayley sum graphs

Minors in small-set expanders

Improved bound on the number of cycle sets

Hypergraph universality via branching random walks

Multipartite nearly orthogonal sets over finite fields

The number of arcs in Fq2​ of a given cardinality

Counting sparse induced subgraphs in locally dense graphs

Spread blow-up lemma with an application to perturbed random graphs

Short proof of the hypergraph container theorem

The largest subgraph without a forbidden induced subgraph

The Hamilton space of pseudorandom graphs

Global rigidity of random graphs in R

Universality for graphs with bounded density

Edge-disjoint paths in expanders: online with removals

A short note on the characterization of countable chains with finite big Ramsey spectra

Routing permutations on spectral expanders via matchings

Probabilistic intuition holds for a class of small subgraph games

On the size-Ramsey number of grids

The number of arcs in $F_{q}^{2}$ of a given cardinality

Global rigidity of random graphs in $R$