2 citations · 4 across the 6 of their papers we have counts for
16 papers
Routing permutations on spectral expanders via matchings
Rajko Nenadov
We consider the following matching-based routing problem. Initially, each vertex of a connected graph is occupied by a pebble which has a unique destination . In each…
Small subsets without -term arithmetic progressions
Rajko Nenadov
Szemerédi's theorem implies that there are subsets of which do not contain a -term arithmetic progression. A sparse analogue of this statement was obtained by B…
A new proof of the KŁR conjecture
Rajko Nenadov
Estimating the probability that the Erdős-Rényi random graph is -free, for a fixed graph , is one of the fundamental problems in random graph theory. If is such…
An O(n) time algorithm for finding Hamilton cycles with high probability
Rajko Nenadov, Angelika Steger, Pascal Su
We design a randomized algorithm that finds a Hamilton cycle in time with high probability in a random graph with edge probability . T…
Rolling backwards can move you forward: on embedding problems in sparse expanders
Nemanja Draganić, Michael Krivelevich, Rajko Nenadov
We develop a general embedding method based on the Friedman-Pippenger tree embedding technique (1987) and its algorithmic version, essentially due to Aggarwal et al. (1996), enhanc…
The size-Ramsey number of short subdivisions
Nemanja Draganić, Michael Krivelevich, Rajko Nenadov
The -size-Ramsey number of a graph is the smallest number of edges a graph can have, such that for every edge-coloring of with colors there exists…