2 citations · 7 across the 7 of their papers we have counts for
13 papers · 1 filter
Covering cycles in sparse graphs
Frank Mousset, Nemanja Škorić, Miloš Trujić
Let be an integer. Kouider and Lonc proved that the vertex set of every graph with vertices and minimum degree at least can be covered by $k -…
Triangle resilience of the square of a Hamilton cycle in random graphs
Manuela Fischer, Nemanja Škorić, Angelika Steger +1
Since first introduced by Sudakov and Vu in 2008, the study of resilience problems in random graphs received a lot of attention in probabilistic combinatorics. Of particular intere…
Monochromatic cycle covers in random graphs
Dániel Korándi, Frank Mousset, Rajko Nenadov +2
A classic result of Erdős, Gyárfás and Pyber states that for every coloring of the edges of with colors, there is a cover of its vertex set by at most $f(r) = O(r^2 \log…
Local resilience of an almost spanning -cycle in random graphs
Nemanja Škorić, Angelika Steger, Miloš Trujić
The famous Pósa-Seymour conjecture, confirmed in 1998 by Komlós, Sárközy, and Szemerédi, states that for any , every graph on vertices with minimum degree $kn/(k + 1)…
Smaller subgraphs of minimum degree k
Frank Mousset, Andreas Noever, Nemanja Škorić
In 1990 Erdős, Faudree, Rousseau and Schelp proved that for , every graph with vertices and edges contains a subgraph of minimu…
On Komlós' tiling theorem in random graphs
Rajko Nenadov, Nemanja Škorić
Conlon, Gowers, Samotij, and Schacht showed that for a given graph and a constant , there exists such that if then asymptotically almost su…
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 , which is not a forest of stars and paths of length , and fixed number of colours there exist p…
A tight Erdős-Pósa function for long cycles
Frank Mousset, Andreas Noever, Nemanja Škorić +1
A classic result of Erdős and Pósa says that any graph contains either vertex-disjoint cycles or can be made acyclic by deleting at most vertices. Here we general…
Powers of Hamilton cycles in random graphs and tight Hamilton cycles in random hypergraphs
Rajko Nenadov, Nemanja Škorić
We show that for every there exists such that if then asymptotically almost surely the random graph contains the \t…
Almost-spanning universality in random graphs
David Conlon, Asaf Ferber, Rajko Nenadov +1
A graph is said to be -universal if it contains every graph on vertices with maximum degree at most . It is known that for any and any…
Robust hamiltonicity of random directed graphs
Asaf Ferber, Rajko Nenadov, Andreas Noever +2
In his seminal paper from 1952 Dirac showed that the complete graph on vertices remains Hamiltonian even if we allow an adversary to remove edges tou…
An algorithmic framework for obtaining lower bounds for random Ramsey problems
Rajko Nenadov, Yury Person, Nemanja Škorić +1
In this paper we introduce a general framework for proving lower bounds for various Ramsey type problems within random settings. The main idea is to view the problem from an algori…
On finite reflexive homomorphism-homogeneous binary relational systems
Dragan Mašulović, Rajko Nenadov, Nemanja Škorić
A structure is called homogeneous if every isomorphism between finitely induced substructures of the structure extends to an automorphism of the structure. Recently, P. J. Cameron…