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

Showing 2025Show all

5 papers · 1 filter

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…