Zobrazeno 1 - 10
of 47
pro vyhledávání: '"Trujić, Miloš"'
Autor:
Sulser, Aurelio, Trujić, Miloš
For a graph $H$ and an integer $n$, we let $nH$ denote the disjoint union of $n$ copies of $H$. In 1975, Burr, Erd\H{o}s, and Spencer initiated the study of Ramsey numbers for $nH$, one of few instances for which Ramsey numbers are now known precisel
Externí odkaz:
http://arxiv.org/abs/2212.02455
Autor:
Petrova, Kalina, Trujić, Miloš
A loose Hamilton cycle in a hypergraph is a cyclic sequence of edges covering all vertices in which only every two consecutive edges intersect and do so in exactly one vertex. With Dirac's theorem in mind, it is natural to ask what minimum $d$-degree
Externí odkaz:
http://arxiv.org/abs/2205.11421
We show that the size-Ramsey number of the $\sqrt{n} \times \sqrt{n}$ grid graph is $O(n^{5/4})$, improving a previous bound of $n^{3/2 + o(1)}$ by Clemens, Miralaei, Reding, Schacht, and Taraz.
Comment: 8 pages, 1 figure
Comment: 8 pages, 1 figure
Externí odkaz:
http://arxiv.org/abs/2202.01654
Autor:
Trujić, Miloš
In a recent work, Allen, B\"{o}ttcher, H\`{a}n, Kohayakawa, and Person provided a first general analogue of the blow-up lemma applicable to sparse (pseudo)random graphs thus generalising the classic tool of Koml\'{o}s, S\'{a}rk\"{o}zy, and Szemer\'{e
Externí odkaz:
http://arxiv.org/abs/2111.09236
We show that the size-Ramsey number of any cubic graph with $n$ vertices is $O(n^{8/5})$, improving a bound of $n^{5/3 + o(1)}$ due to Kohayakawa, R\"{o}dl, Schacht, and Szemer\'{e}di. The heart of the argument is to show that there is a constant $C$
Externí odkaz:
http://arxiv.org/abs/2110.01897
The chromatic number $\chi(G)$ of a graph $G$, that is, the smallest number of colors required to color the vertices of $G$ so that no two adjacent vertices are assigned the same color, is a classic and extensively studied parameter. Here we consider
Externí odkaz:
http://arxiv.org/abs/2007.07700
Let $k \geq 2$ be an integer. Kouider and Lonc proved that the vertex set of every graph $G$ with $n \geq n_0(k)$ vertices and minimum degree at least $n/k$ can be covered by $k - 1$ cycles. Our main result states that for every $\alpha > 0$ and $p =
Externí odkaz:
http://arxiv.org/abs/2003.03311
Autor:
Bertschinger, Daniel, Lengler, Johannes, Martinsson, Anders, Meier, Robert, Steger, Angelika, Trujić, Miloš, Welzl, Emo
Consider the following simple coloring algorithm for a graph on $n$ vertices. Each vertex chooses a color from $\{1, \dotsc, \Delta(G) + 1\}$ uniformly at random. While there exists a conflicted vertex choose one such vertex uniformly at random and r
Externí odkaz:
http://arxiv.org/abs/2002.05121
Autor:
Nenadov, Rajko, Trujić, Miloš
A seminal result by Koml\'os, Sark\"ozy, and Szemer\'edi states that if a graph $G$ with $n$ vertices has minimum degree at least $kn/(k + 1)$, for some $k \in \mathbb{N}$ and $n$ sufficiently large, then it contains the $k$-th power of a Hamilton cy
Externí odkaz:
http://arxiv.org/abs/1811.09209
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 interest are resilience problems of spanning structures. It is known that fo
Externí odkaz:
http://arxiv.org/abs/1809.07534