Source author record

Jozef Skokan

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

9works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

A robust Corrádi--Hajnal Theorem

For a graph $G$ and $p\in[0,1]$ , we denote by $G_p$ the random sparsification of $G$ obtained by keeping each edge of $G$ independently, with probability $p$ . We show that there exists a $C>0$ such that if $p\geq C(\log n)^{1/3}n^{-2/3}$ and $G$ is an $n$ -vertex graph with $n\in 3\mathbb{N}$ and $δ(G)\geq \tfrac{2n}{3}$ , then with high probability $G_p$ contains a triangle factor. Both the minimum degree condition and the probability condition, up to the choice of $C$ , are tight. Our result can be viewed as a common strengthening of the seminal theorems of Corrádi and Hajnal, which deals with the extremal minimum degree condition for containing triangle factors (corresponding to $p=1$ in our result), and Johansson, Kahn and Vu, which deals with the threshold for the appearance of a triangle factor in $G(n,p)$ (corresponding to $G=K_n$ in our result). It also implies a lower bound on the number of triangle factors in graphs with minimum degree at least $\tfrac{2n}{3}$ which gets close to the truth.

preprint2022arXiv

Triangles in randomly perturbed graphs

We study the problem of finding pairwise vertex-disjoint triangles in the randomly perturbed graph model, which is the union of any $n$ -vertex graph $G$ satisfying a given minimum degree condition and the binomial random graph $G(n,p)$ . We prove that asymptotically almost surely $G \cup G(n,p)$ contains at least $\min\{δ(G), \lfloor n/3 \rfloor\}$ pairwise vertex-disjoint triangles, provided $p \ge C \log n/n$ , where $C$ is a large enough constant. This is a perturbed version of an old result of Dirac. Our result is asymptotically optimal and answers a question of Han, Morris, and Treglown [RSA, 2021, no. 3, 480--516] in a strong form. We also prove a stability version of our result, which in the case of pairwise vertex-disjoint triangles extends a result of Han, Morris, and Treglown [RSA, 2021, no. 3, 480--516]. Together with a result of Balogh, Treglown, and Wagner [CPC, 2019, no. 2, 159--176] this fully resolves the existence of triangle factors in randomly perturbed graphs. We believe that the methods introduced in this paper are useful for a variety of related problems: we discuss possible generalisations to clique factors, cycle factors, and $2$ -universality.

preprint2020arXiv

Partitioning edge-coloured hypergraphs into few monochromatic tight cycles

Confirming a conjecture of Gyárfás, we prove that, for all natural numbers $k$ and $r$ , the vertices of every $r$ -edge-coloured complete $k$ -uniform hypergraph can be partitioned into a bounded number (independent of the size of the hypergraph) of monochromatic tight cycles. We further prove that, for for all natural numbers $p$ and $r$ , the vertices of every $r$ -edge-coloured complete graph can be partitioned into a bounded number of $p$ -th powers of cycles, settling a problem of Elekes, Soukup, Soukup and Szentmiklóssy. In fact we prove a common generalisation of both theorems which further extends these results to all host hypergraphs of bounded independence number.

preprint2019arXiv

Decomposing tournaments into paths

We consider a generalisation of Kelly's conjecture which is due to Alspach, Mason, and Pullman from 1976. Kelly's conjecture states that every regular tournament has an edge decomposition into Hamilton cycles, and this was proved by Kühn and Osthus for large tournaments. The conjecture of Alspach, Mason, and Pullman asks for the minimum number of paths needed in a path decomposition of a general tournament $T$ . There is a natural lower bound for this number in terms of the degree sequence of $T$ and it is conjectured that this bound is correct for tournaments of even order. Almost all cases of the conjecture are open and we prove many of them.

preprint2016arXiv

Exact Ramsey numbers of odd cycles via nonlinear optimisation

For a graph $G$ , the $k$ -colour Ramsey number $R_k(G)$ is the least integer $N$ such that every $k$ -colouring of the edges of the complete graph $K_N$ contains a monochromatic copy of $G$ . Let $C_n$ denote the cycle on $n$ vertices. We show that for fixed $k\geq2$ and $n$ odd and sufficiently large, $R_k(C_n)=2^{k-1}(n-1)+1.$ This resolves a conjecture of Bondy and Erdős [J. Combin. Th. Ser. B \textbf{14} (1973), 46--54] for large $n$ . The proof is analytic in nature, the first step of which is to use the regularity method to relate this problem in Ramsey theory to one in nonlinear optimisation. This allows us to prove a stability-type generalisation of the above and establish a surprising correspondence between extremal $k$ -colourings for this problem and perfect matchings in the $k$ -dimensional hypercube $Q_k$ .

preprint2013arXiv

Maximum planar subgraphs in dense graphs

Kühn, Osthus and Taraz showed that for each γ>0 there exists C such that any n-vertex graph with minimum degree γn contains a planar subgraph with at least 2n-C edges. We find the optimum value of C for all γ<1/2 and sufficiently large n.

preprint2013arXiv

On the Ramsey number of the triangle and the cube

The Ramsey number r(K_3,Q_n) is the smallest integer N such that every red-blue colouring of the edges of the complete graph K_N contains either a red n-dimensional hypercube, or a blue triangle. Almost thirty years ago, Burr and Erdős conjectured that r(K_3,Q_n) = 2^{n+1} - 1 for every n \in \N, but the first non-trivial upper bound was obtained only recently, by Conlon, Fox, Lee and Sudakov, who proved that r(K_3,Q_n) \le 7000 \cdot 2^n. Here we show that r(K_3,Q_n) = (1 + o(1)) 2^{n+1} as n \to \infty.

preprint2010arXiv

On the Multi-coloured Ramsey Numbers of Cycles

For a graph $L$ and an integer $k\geq 2$ , $R_k(L)$ denotes the smallest integer $N$ for which for any edge-colouring of the complete graph $K_N$ by $k$ colours there exists a colour $i$ for which the corresponding colour class contains $L$ as a subgraph. Bondy and Erdős conjectured that for an odd cycle $C_n$ on $n$ vertices, $R_k(C_n) = 2^{k-1}(n-1)+1 \text{for $n>3$.}$ They proved the case when $k=2$ and also provided an upper bound $R_k(C_n)\leq (k+2)!n$ . Recently, this conjecture has been verified for $k=3$ if $n$ is large. In this note, we prove that for every integer $k\geq 4$ , $R_k(C_n)\leq k2^kn+o(n), \text{as $n\to\infty$.}$ When $n$ is even, Yongqi, Yuansheng, Feng, and Bingxi gave a construction, showing that $R_k(C_n)\geq (k-1)n-2k+4.$ Here we prove that if $n$ is even, then $R_k(C_n)\leq kn+o(n), \text{as $n\to\infty$.}$

preprint2010arXiv

Ramsey-goodness -- and otherwise

A celebrated result of Chvátal, Rödl, Szemerédi and Trotter states (in slightly weakened form) that, for every natural number $Δ$ , there is a constant $r_Δ$ such that, for any connected $n$ -vertex graph $G$ with maximum degree $Δ$ , the Ramsey number $R(G,G)$ is at most $r_Δn$ , provided $n$ is sufficiently large. In 1987, Burr made a strong conjecture implying that one may take $r_Δ= Δ$ . However, Graham, Rödl and Ruciński showed, by taking $G$ to be a suitable expander graph, that necessarily $r_Δ> 2^{cΔ}$ for some constant $c>0$ . We show that the use of expanders is essential: if we impose the additional restriction that the bandwidth of $G$ be at most some function $β(n) = o(n)$ , then $R(G,G) \le (2χ(G)+4)n\leq (2Δ+6)n$ , i.e., $r_Δ= 2Δ+6$ suffices. On the other hand, we show that Burr's conjecture itself fails even for $P_n^k$ , the $k$ th power of a path $P_n$ . Brandt showed that for any $c$ , if $Δ$ is sufficiently large, there are connected $n$ -vertex graphs $G$ with $Δ(G)\leqΔ$ but $R(G,K_3)>cn$ . We show that, given $Δ$ and $H$ , there are $β>0$ and $n_0$ such that, if $G$ is a connected graph on $n\ge n_0$ vertices with maximum degree at most $Δ$ and bandwidth at most $βn$ , then we have $R(G,H)=(χ(H)-1)(n-1)+σ(H)$ , where $σ(H)$ is the smallest size of any part in any $χ(H)$ -partition of $H$ . We also show that the same conclusion holds without any restriction on the maximum degree of $G$ if the bandwidth of $G$ is at most $ε(H) \log n/\log\log n$ .

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.

Jozef Skokan

Research overview

Is this your work?

9 publications

A robust Corrádi--Hajnal Theorem

Triangles in randomly perturbed graphs

Partitioning edge-coloured hypergraphs into few monochromatic tight cycles

Decomposing tournaments into paths

Exact Ramsey numbers of odd cycles via nonlinear optimisation

Maximum planar subgraphs in dense graphs

On the Ramsey number of the triangle and the cube

On the Multi-coloured Ramsey Numbers of Cycles

Ramsey-goodness -- and otherwise

See the researcher in context

Building this map preview