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 2016Show all

6 papers · 1 filter

math.CO2016

On Komlós' tiling theorem in random graphs

Rajko Nenadov, Nemanja Škorić

Conlon, Gowers, Samotij, and Schacht showed that for a given graph $H$ and a constant $γ > 0$ , there exists $C > 0$ such that if $p \geq C n^{- 1/ m_{2} (H)}$ then asymptotically almost su…

math.CO2016★ 1 cited

Star-factors in graphs of high degree

Rajko Nenadov

We prove that every graph with sufficiently large minimum degree $d$ contains a spanning forest in which every component is a star of size at least $d - O ~ (d^{1/4})$ .…

math.CO2016

Symmetric and asymmetric Ramsey properties in random hypergraphs

Luca Gugelmann, Rajko Nenadov, Yury Person +3

A celebrated result of Rödl and Ruciński states that for every graph $F$ , which is not a forest of stars and paths of length $3$ , and fixed number of colours $r \geq 2$ there exist p…

math.CO2016★ 2 cited

Optimal induced universal graphs for bounded-degree graphs

Noga Alon, Rajko Nenadov

We show that for any constant $Δ \geq 2$ , there exists a graph $G$ with $O (n^{Δ/2})$ vertices which contains every $n$ -vertex graph with maximum degree $Δ$ as an induced subgraph. F…

cs.DM2016★ 6 cited

Unique reconstruction threshold for random jigsaw puzzles

Rajko Nenadov, Pascal Pfister, Angelika Steger

A random jigsaw puzzle is constructed by arranging $n^{2}$ square pieces into an $n \times n$ grid and assigning to each edge of a piece one of $q$ available colours uniformly at ran…

math.CO2016

Powers of Hamilton cycles in random graphs and tight Hamilton cycles in random hypergraphs

Rajko Nenadov, Nemanja Škorić

We show that for every $k \in N$ there exists $C > 0$ such that if $p^{k} \geq C lo g^{8} n / n$ then asymptotically almost surely the random graph $G_{n, p}$ contains the $k$ \t…