BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Rajko Nenadov

Rajko Nenadov appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.CODiscrete MathematicsData Structures and Algorithms

Catalog footprint

What is connected

14works
3topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

14 published item(s)

preprint2022arXiv

Probabilistic intuition holds for a class of small subgraph games

Consider the following two-player game on the edges of $K_n$, the complete graph with $n$ vertices: Starting with an empty graph $G$ on the vertex set of $K_n$, in each round the first player chooses $b \in \mathbb{N}$ edges from $K_n$ which have not previously been chosen, and the second player immediately and irrevocably picks one of these edges and adds it to $G$. We show that for any graph $H$ with at least one edge, if $b < c n^{1/m(H)}$, where $c = c(H) > 0$ only depends on $H$ and $m(H)$ is the usual density function, then the first player can ensure the resulting graph $G$ contains $Ω(n^{v(H)} / b^{e(H)})$ copies of $H$. The bound on $b$ is the best possible apart from the constant $c$ and shows that the density of the resulting graph for which it is possible to enforce the appearance of $H$ coincides with a threshold for the appearance in the Erdős-Rényi random graph. This resolves a conjecture by Bednarska-Bzdȩga, Hefetz, and Luczak and provides a prominent class of games for which probabilistic intuition accurately predicts the outcome. The strategy of the first player is deterministic with polynomial running time, with the degree depending on the size of $H$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Routing permutations on spectral expanders via matchings

We consider the following matching-based routing problem. Initially, each vertex $v$ of a connected graph $G$ is occupied by a pebble which has a unique destination $π(v)$. In each round the pebbles across the edges of a selected matching in $G$ are swapped, and the goal is to route each pebble to its destination vertex in as few rounds as possible. We show that if $G$ is a sufficiently strong $d$-regular spectral expander then any permutation $π$ can be achieved in $O(\log n)$ rounds. This is optimal for constant $d$ and resolves a problem of Alon, Chung, and Graham [SIAM J. Discrete Math., 7 (1994), pp. 516--530].

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The threshold bias of the clique-factor game

Let $r \ge 4$ be an integer and consider the following game on the complete graph $K_n$ for $n \in r \mathbb{Z}$: Two players, Maker and Breaker, alternately claim previously unclaimed edges of $K_n$ such that in each turn Maker claims one and Breaker claims $b \in \mathbb{N}$ edges. Maker wins if her graph contains a $K_r$-factor, that is a collection of $n/r$ vertex-disjoint copies of $K_r$, and Breaker wins otherwise. In other words, we consider a $b$-biased $K_r$-factor Maker-Breaker game. We show that the threshold bias for this game is of order $n^{2/(r+2)}$. This makes a step towards determining the threshold bias for making bounded-degree spanning graphs and extends a result of Allen et al.\ who resolved the case $r \in \{3,4\}$ up to a logarithmic factor.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Almost-spanning universality in random graphs

A graph $G$ is said to be $\mathcal H(n,Δ)$-universal if it contains every graph on $n$ vertices with maximum degree at most $Δ$. It is known that for any $\varepsilon > 0$ and any natural number $Δ$ there exists $c > 0$ such that the random graph $G(n,p)$ is asymptotically almost surely $\mathcal H((1-\varepsilon)n,Δ)$-universal for $p \geq c (\log n/n)^{1/Δ}$. Bypassing this natural boundary, we show that for $Δ\geq 3$ the same conclusion holds when $p = ω\left(n^{-\frac{1}{Δ-1}}\log^5 n\right)$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On Komlós' tiling theorem in random graphs

Conlon, Gowers, Samotij, and Schacht showed that for a given graph $H$ and a constant $γ> 0$, there exists $C > 0$ such that if $p \ge Cn^{-1/m_2(H)}$ then asymptotically almost surely every spanning subgraph $G$ of the random graph $\mathcal{G}(n,p)$ with minimum degree at least $δ(G) \ge (1 - 1/χ_{\mathrm{cr}}(H) + γ)np$ contains an $H$-packing that covers all but at most $γn$ vertices. Here, $χ_{\mathrm{cr}}(H)$ denotes the critical chromatic threshold, a parameter introduced by Komlós. We show that this theorem can be bootstraped to obtain an $H$-packing covering all but at most $γ(C/p)^{m_2(H)}$ vertices, which is strictly smaller when $p > C n^{-1/m_2(H)}$. In the case where $H = K_3$ this answers the question of Balogh, Lee, and Samotij. Furthermore, we give an upper bound on the size of an $H$-packing for certain ranges of $p$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Unique reconstruction threshold for random jigsaw puzzles

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 random, with the restriction that touching edges receive the same colour. We show that if $q = o(n)$ then with high probability such a puzzle does not have a unique solution, while if $q \ge n^{1 + \varepsilon}$ for any constant $\varepsilon > 0$ then the solution is unique. This solves a conjecture of Mossel and Ross (Shotgun assembly of labeled graphs, arXiv:1504.07682).

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

An algorithmic framework for obtaining lower bounds for random Ramsey problems

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 algorithmic perspective: we aim at providing an algorithm that finds the desired colouring with high probability. Our framework allows to reduce the probabilistic problem of whether the Ramsey property at hand holds for random (hyper)graphs with edge probability $p$ to a deterministic question of whether there exists a finite graph that forms an obstruction. In the second part of the paper we apply this framework to address and solve various open problems. In particular, we extend the result of Bohman, Frieze, Pikhurko and Smyth (2010) for bounded anti-Ramsey problems in random graphs to the case of $2$ colors and to hypergraph cliques. As a corollary, this proves a matching lower bound for the result of Friedgut, Rödl and Schacht (2010) and, independently, Conlon and Gowers (2014+) for the classical Ramsey problem for hypergraphs in the case of cliques. Finally, we provide matching lower bounds for a proper-colouring version of anti-Ramsey problems introduced by Kohayakawa, Konstadinidis and Mota~(2014) in the case of cliques and cycles.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On the number of graphs without large cliques

In 1976 Erdos, Kleitman and Rothschild determined the number of graphs without a clique of size $\ell$. In this note we extend their result to the case of forbidden cliques of increasing size. More precisely we prove that for $\ell_n \le \frac12(\log n)^{1/4}$ there are $$2^{(1-1/(\ell_n-1))n^2/2+o(n^2/\ell_n)}$$ $K_{\ell_n}$-free graphs of order $n$. Our proof is based on the recent hypergraph container theorems of Saxton, Thomason and Balogh, Morris, Samotij, in combination with a theorem of Lovasz and Simonovits.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

On the threshold for the Maker-Breaker $H$-game

We study the Maker-Breaker $H$-game played on the edge set of the random graph $G_{n,p}$. In this game two players, Maker and Breaker, alternately claim unclaimed edges of $G_{n,p}$, until all the edges are claimed. Maker wins if he claims all the edges of a copy of a fixed graph $H$; Breaker wins otherwise. In this paper we show that, with the exception of trees and triangles, the threshold for an $H$-game is given by the threshold of the corresponding Ramsey property of $G_{n,p}$ with respect to the graph $H$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Robust hamiltonicity of random directed graphs

In his seminal paper from 1952 Dirac showed that the complete graph on $n\geq 3$ vertices remains Hamiltonian even if we allow an adversary to remove $\lfloor n/2\rfloor$ edges touching each vertex. In 1960 Ghouila-Houri obtained an analogue statement for digraphs by showing that every directed graph on $n\geq 3$ vertices with minimum in- and out-degree at least $n/2$ contains a directed Hamilton cycle. Both statements quantify the robustness of complete graphs (digraphs) with respect to the property of containing a Hamilton cycle. A natural way to generalize such results to arbitrary graphs (digraphs) is using the notion of \emph{local resilience}. The local resilience of a graph (digraph) $G$ with respect to a property $\mathcal{P}$ is the maximum number $r$ such that $G$ has the property $\mathcal{P}$ even if we allow an adversary to remove an $r$-fraction of (in- and out-going) edges touching each vertex. The theorems of Dirac and Ghouila-Houri state that the local resilience of the complete graph and digraph with respect to Hamiltonicity is $1/2$. Recently, this statements have been generalized to random settings. Lee and Sudakov (2012) proved that the local resilience of a random graph with edge probability $p=ω(\log n /n)$ with respect to Hamiltonicity is $1/2\pm o(1)$. For random directed graphs, Hefetz, Steger and Sudakov (2014+) proved an analogue statement, but only for edge probability $p=ω(\log n/\sqrt{n})$. In this paper we significantly improve their result to $p=ω(\log^8 n/ n)$, which is optimal up to the polylogarithmic factor.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Universality of random graphs and rainbow embedding

In this paper we show how to use simple partitioning lemmas in order to embed spanning graphs in a typical member of $G(n,p)$. Let the \emph{maximum density} of a graph $H$ be the maximum average degree of all the subgraphs of $H$. First, we show that for $p=ω(Δ^{12} n^{-1/2d}\log^3n)$, a graph $G\sim G(n,p)$ w.h.p.\ contains copies of all spanning graphs $H$ with maximum degree at most $Δ$ and maximum density at most $d$. For $d<Δ/2$, this improves a result of Dellamonica, Kohayakawa, Rödl and Rucińcki. Next, we show that if we additionally restrict the spanning graphs to have girth at least 7 then the random graph contains w.h.p.\ all such graphs for $p=ω(Δ^{12} n^{-1/d}\log^3n)$. In particular, if $p=ω(Δ^{12} n^{-1/2}\log^3 n)$, the random graph therefore contains w.h.p.\ every spanning tree with maximum degree bounded by $Δ$. This improves a result of Johannsen, Krivelevich and Samotij. Finally, in the same spirit, we show that for any spanning graph $H$ with constant maximum degree, and for suitable $p$, if we randomly color the edges of a graph $G\sim G(n,p)$ with $(1 + o(1))|E(H)|$ colors, then w.h.p.\ there exists a \emph{rainbow} copy of $H$ in $G$ (that is, a copy of $H$ with all edges colored with distinct colors).

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Finite irreflexive homomorphism-homogeneous binary relational systems

A structure is called homogeneous if every isomorphism between finite substructures of the structure extends to an automorphism of the structure. Recently, P. J. Cameron and J. Nešetřil introduced a relaxed version of homogeneity: we say that a structure is homomorphism-homogeneous if every homomorphism between finite substructures of the structure extends to an endomorphism of the structure. In this paper we characterize all finite homomorphism-homogeneous relational systems with one irreflexive binary relation.

0 citations0 reviewsNo code linkedOpen access