Zobrazeno 1 - 10
of 147
pro vyhledávání: '"Nenadov, Rajko"'
Autor:
Nenadov, Rajko, Pham, Huy Tuan
Combining ideas of Pham, Sah, Sawhney, and Simkin on spread perfect matchings in super-regular bipartite graphs with an algorithmic blow-up lemma, we prove a spread version of the blow-up lemma. Intuitively, this means that there exists a probability
Externí odkaz:
http://arxiv.org/abs/2410.06132
Autor:
Nenadov, Rajko, Pham, Huy Tuan
We present a short and simple proof of the celebrated hypergraph container theorem of Balogh--Morris--Samotij and Saxton--Thomason. On a high level, our argument utilises the idea of iteratively taking vertices of largest degree from an independent s
Externí odkaz:
http://arxiv.org/abs/2408.08514
We initiate the systematic study of the following Tur\'an-type question. Suppose $\Gamma$ is a graph with $n$ vertices such that the edge density between any pair of subsets of vertices of size at least $t$ is at most $1 - c$, for some $t$ and $c > 0
Externí odkaz:
http://arxiv.org/abs/2405.05902
We show that if $n$ is odd and $p \ge C \log n / n$, then with high probability Hamilton cycles in $G(n,p)$ span its cycle space. More generally, we show this holds for a class of graphs satisfying certain natural pseudorandom properties. The proof i
Externí odkaz:
http://arxiv.org/abs/2402.01447
Consider the Erd\H{o}s-R\'enyi random graph process $\{G_m\}_{m \ge 0}$ in which we start with an empty graph $G_0$ on the vertex set $[n]$, and in each step form $G_i$ from $G_{i-1}$ by adding one new edge chosen uniformly at random. Resolving a con
Externí odkaz:
http://arxiv.org/abs/2401.10803
A graph $G$ is $\textit{universal}$ for a (finite) family $\mathcal{H}$ of graphs if every $H \in \mathcal{H}$ is a subgraph of $G$. For a given family $\mathcal{H}$, the goal is to determine the smallest number of edges an $\mathcal{H}$-universal gr
Externí odkaz:
http://arxiv.org/abs/2311.05500
Autor:
Draganić, Nemanja, Nenadov, Rajko
We consider the problem of finding edge-disjoint paths between given pairs of vertices in a sufficiently strong $d$-regular expander graph $G$ with $n$ vertices. In particular, we describe a deterministic, polynomial time algorithm which maintains an
Externí odkaz:
http://arxiv.org/abs/2310.13082
In this short note we confirm the deep structural correspondence between the complexity of a countable scattered chain (= strict linear order) and its big Ramsey combinatorics: we show that a countable scattered chain has finite big Ramsey degrees if
Externí odkaz:
http://arxiv.org/abs/2305.02648
Autor:
Nenadov, Rajko
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 $\pi(v)$. In each round the pebbles across the edges of a selected matching in $G$ ar
Externí odkaz:
http://arxiv.org/abs/2209.03838
Autor:
Nenadov, Rajko
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
Externí odkaz:
http://arxiv.org/abs/2207.02772