Nemanja Draganić
Postdoctoral researcher
University of Oxford
University of Oxford
My main research interests lie in discrete mathematics and its intersections with theoretical computer science. In particular, I am interested in extremal and probabilistic combinatorics, Ramsey theory, random graph theory, and combinatorial and algorithmic aspects of expander graphs.
I was runner up for the Richard Rado prize. My research on Hamiltonicity in expanders was featured in the popular science magazine Quanta.
Winner of B92.net's 'Virtuelni selektor' Fantasy Basketball Competition during the 2023 FIBA World Cup — perhaps a bit out of place here...
Selected publications
Draganić, N., Montgomery R., Munhá Correia, D., Pokrovskiy, A. and Sudakov B. (2024),
Hamiltonicity of expanders: optimal bounds and applications, submitted (check out the article in Quanta Magazine on this work)
An n-vertex graph G is a C-expander if |N(X)| ≥ C|X| for every X ⊆ V(G) with |X| < n/2C and there is an edge between every two disjoint sets of at least n/2C vertices. We show that there is some constant C > 0 for which every C-expander is Hamiltonian. In particular, this implies the well-known conjecture of Krivelevich and Sudakov from 2003 on Hamilton cycles in (n,d,λ)-graphs. This completes a long line of research on the Hamiltonicity of sparse graphs and has many applications, including to the Hamiltonicity of random Cayley graphs.
Draganić, N., Munhá Correia, D., Sudakov, B. (2024). Pancyclicity of Hamiltonian graphs,
Journal of European Mathematical Society, published online
An n-vertex graph is Hamiltonian if it contains a cycle that covers all of its vertices, and it is pancyclic if it contains cycles of all lengths from 3 up to n. In 1972, Erdős conjectured that every Hamiltonian graph with independence number at most k and at least n = Ω(k^2) vertices is pancyclic. In this paper, we prove this old conjecture in a strong form by showing that if such a graph has n = (2 + o(1))k^2 vertices, it is already pancyclic, and this bound is asymptotically best possible.
Draganić, N., Petrova, K. (2025). The size-Ramsey number of graphs with maximum degree three,
Journal of the London Mathematical Society, published online
The size-Ramsey number of a graph H is the smallest number of edges a host graph G can have, such that for any red/blue coloring of G, there is a monochromatic copy of H in G. Conlon, Nenadov, and Trujić showed that if H is a graph with n vertices and maximum degree three, then the size-Ramsey number is O(n^(8/5)), improving upon the previous upper bound of n^(5/3+o(1)) by Kohayakawa, Rödl, Schacht, and Szemerédi. In this paper, we show that the size-Ramsey number is at most n^(3/2+o(1)). While previous results used binomial random graphs as host graphs, we achieve our result using a novel host graph construction. Our bound hits a natural barrier of the existing methods.
Draganić, N., Krivelevich, M. and Nenadov R. (2021). Rolling backwards can move you forward: on embedding problems in sparse expanders, Transactions of American Mathematical Society 375: 5195-5216
We develop a general embedding method based on the Friedman-Pippenger tree embedding technique and its algorithmic version, enhanced with a roll-back idea allowing a sequential retracing of previously performed embedding steps. We use this method to obtain the following results:
We show that the size-Ramsey number of logarithmically long subdivisions of bounded degree graphs is linear in their number of vertices, settling a conjecture of Pak (2002).
We give a deterministic, polynomial time online algorithm for finding vertex-disjoint paths of a prescribed length between given pairs of vertices in an expander graph. Our result answers a question of Alon and Capalbo (2007).
We show that relatively weak bounds on the spectral ratio λ/d of d-regular graphs force the existence of a topological minor of Kt where t = (1 − o(1))d. We also exhibit a construction which shows that the theoretical maximum t = d + 1 cannot be attained even if λ = O(√d). This answers a question of Fountoulakis, Kühn, and Osthus (2009).
Bradač, D., Draganić, N., and Sudakov, B. (2024). Effective bounds for induced size-Ramsey numbers of cycles,
Combinatorica 44, 1011–1039
The induced size-Ramsey number of a graph is the smallest number of edges a host graph can have, such that no matter how its edges are colored with a certain number of colors, there will always be a monochromatic copy of the original graph as an induced subgraph. In 1995, Haxell, Kohayakawa, and Łuczak showed that for cycles, these numbers are linear in the size of the cycle for any constant number of colors. This result was achieved using the regularity lemma, which led to a very large, tower-type dependence on the number of colors.
In our work, we significantly improve these bounds, showing that the induced size-Ramsey number for cycles has a much smaller dependence on the number of colors. Specifically, for even-sized cycles, the number grows polynomially with the number of colors, and for odd-sized cycles, we show upper bounds very close to the known lower bounds. Additionally, we prove essentially optimal bounds for the normal (non-induced) size-Ramsey number for odd cycles, showing that they grow exponentially in the number of colors. Our approach involves a new construction of the host graph, which simplifies the problem to finding a cycle of a certain length in a graph with local sparsity.
Draganić, N., Keevash, P., Müyesser, A. (2025), Cyclic subsets in regular Dirac graphs,
International Mathematics Research Notices, accepted
In 1996, in his final paper, Erdős posed the following question together with Faudree: Is there a positive constant c such that every (n+1)-regular graph on 2n vertices contains at least c·2^(2n) distinct subsets of vertices that are cyclic, meaning each subset exactly forms the vertex set of a cycle?
We answer this question affirmatively and in a strong form. Specifically, we prove the following exact result: for all sufficiently large n, the graph that minimizes the number of such cyclic subsets is constructed by taking the complete bipartite graph with parts of size n−1 and n+1, and adding a 2-factor (a spanning collection of vertex-disjoint cycles) within the larger part.
In particular, this implies that for large n, the optimal constant c is exactly one-half.
A linear forest is a collection of vertex‑disjoint paths. The Linear Arboricity Conjecture states that any graph of maximum degree Δ can be decomposed into at most ⌈(Δ + 1)/2⌉ linear forests. We prove that Δ/2 + O(log n) linear forests suffice, where n is the number of vertices of the graph. If Δ = Ω(n^ε), this represents an exponential improvement over the previous best error term. Our approach generalizes Pósa rotations—from rotating a single path endpoint to performing simultaneous rotations on multiple endpoints within a linear forest. This technique also resolves a conjecture of Feige and Fuchs on spanning linear forests with few paths and establishes the existence of optimally short tours in connected regular graphs.
Draganić, N, Kim, J., Lee, H., Munhá Correia, D., Pavez-Signé, M., Sudakov, B. (2025),
Hamilton cycles in pseudorandom graphs: resilience and approximate decompositions
Dirac’s classical theorem shows that dense graphs with minimum degree at least n/2 are Hamiltonian, and later work proved that regular such graphs even decompose into Hamilton cycles, resolving the Nash–Williams conjecture. In the pseudorandom setting, it was long conjectured that analogous results hold in much sparser graphs. We establish asymptotically optimal theorems on resilience and Hamilton decompositions in sparse pseudorandom graphs, substantially improving previous results.