Source author record

Nemanja Draganić

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

5works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

Cycles with almost linearly many chords

We prove that constant minimum degree already forces cycles with almost linearly many chords. Specifically, every graph $G$ with $δ(G)\ge C$ contains a cycle of length $\ell\ge 4$ with $Ω(\ell/\log^{C}\ell)$ chords for some absolute constant $C>0$ . This is the first result showing that a constant-degree condition yields an unbounded -- indeed nearly linear -- number of chords, placing our bound within a polylogarithmic factor of the Chen--Erdős--Staton conjecture. It also gives a strong affirmative conclusion in the direction of a recent question of Dvořák, Martins, Thomassé, and Trotignon asking whether constant-degree graphs must contain cycles whose chord counts grow with their length.

preprint2022arXiv

Short proofs for long induced paths

We present a modification of the Depth first search algorithm, suited for finding long induced paths. We use it to give simple proofs of the following results. We show that the induced size-Ramsey number of paths satisfies $\hat{R}_{\mathrm{ind}}(P_n)\leq 5\cdot 10^7n$ , thus giving an explicit constant in the linear bound, improving the previous bound with a large constant from a regularity lemma argument by Haxell, Kohayakawa and Łuczak. We also provide a bound for the $k$ -color version, showing that $\hat{R}_{\mathrm{ind}}^k(P_n)=O(k^3\log^4k)n$ . Finally, we present a new short proof of the fact that the binomial random graph in the supercritical regime, $G(n,\frac{1+\varepsilon}{n})$ , contains typically an induced path of length $Θ(\varepsilon^2) n$ .

preprint2022arXiv

The largest hole in sparse random graphs

We show that for any $d=d(n)$ with $d_0(ε) \le d =o(n)$ , with high probability, the size of a largest induced cycle in the random graph $G(n,d/n)$ is $(2\pm ε)\frac{n}{d}\log d$ . This settles a long-standing open problem in random graph theory.

preprint2021arXiv

Powers of paths in tournaments

In this short note we prove that every tournament contains the $k$ -th power of a directed path of linear length. This improves upon recent results of Yuster and of Girão. We also give a complete solution for this problem when $k=2$ , showing that there is always a square of a directed path of length $\lceil 2n/3 \rceil-1$ , which is best possible.

preprint2020arXiv

Large induced trees in dense random graphs

Erdős and Palka initiated the study of the maximal size of induced trees in random graphs in 1983. They proved that for every fixed $0<p<1$ the size of a largest induced tree in $G_{n,p}$ is concentrated around $2\log_q (np)$ with high probability, where $q=(1-p)^{-1}$ . De la Vega showed concentration around the same value for $p=C/n$ where $C$ is a large constant, and his proof also works for all larger $p$ . We show that for any given tree $T$ with bounded maximum degree and of size $(2-o(1))\log_q(np)$ , $G_{n,p}$ contains an induced copy of $T$ with high probability for $n^{-1/2}\ln^{10/9}n\leq p\leq 0.99$ . This is asymptotically optimal.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.