1 January 2020 in SIAM Journal on Discrete Mathematics
Confirming a conjecture of Gyárfás, we prove that, for all natural numbers $k$ and $r$, the vertices of every $r$-edge-colored 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 all natural numbers $p$ and $r$, the vertices of every $r$-edge-colored 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 [ Discrete Math., 340 (2017), pp. 2053--2069]. In fact we prove a common generalization of both theorems which further extends these results to all host hypergraphs of bounded independence number.
18 January 2020 in Graphs and Combinatorics
Extending a result of Rado to hypergraphs, we prove that for all $$s, k, t \in {\mathbb {N}}$$ with $$k \ge t \ge 2$$ , the vertices of every $$r = s(k-t+1)$$ -edge-coloured countably infinite complete k-graph can be partitioned into the cores of at most s monochromatic t-tight Berge-paths of different colours. We further describe a construction showing that this result is best possible.
22 May 2025 in Forum of Mathematics, Sigma
In 1967, Gerencsér and Gyárfás [16] proved a result which is considered the starting point of graph-Ramsey theory: In every 2-coloring of $K_n$ , there is a monochromatic path on $\lceil (2n+1)/3\rceil $ vertices, and this is best possible. There have since been hundreds of papers on graph-Ramsey theory with some of the most important results being motivated by a series of conjectures of Burr and Erdős [2, 3] regarding the Ramsey numbers of trees (settled in [31]), graphs with bounded maximum degree (settled in [5]), and graphs with bounded degeneracy (settled in [23]). In 1993, Erdős and Galvin [13] began the investigation of a countably infinite analogue of the Gerencsér and Gyárfás result: What is the largest d such that in every $2$ -coloring of $K_{\mathbb {N}}$ there is a monochromatic infinite path with upper density at least d? Erdős and Galvin showed that $2/3\leq d\leq 8/9$ , and after a series of recent improvements, this problem was finally solved in [7] where it was shown that $d={(12+\sqrt {8})}/{17}$ . This paper begins a systematic study of quantitative countably infinite graph-Ramsey theory, focusing on infinite analogues of the Burr-Erdős conjectures. We obtain some results which are analogous to what is known in finite case, and other (unexpected) results which have no analogue in the finite case.
1 October 2020 in European Journal of Combinatorics
21 November 2023 in Combinatorica
1 June 2018 in European Journal of Combinatorics
A finite set A⊂Rd <!--mathContainer--> <!--Loading Mathjax--> is called diameter-Ramsey if for every r∈N <!--mathContainer--> <!--Loading Mathjax--> , there exists some n∈N <!--mathContainer--> <!--Loading Mathjax--> and a finite set B⊂Rn <!--mathContainer--> <!--Loading Mathjax--> with diam(A)=diam(B) <!--mathContainer--> <!--Loading Mathjax--> such that whenever B <!--mathContainer--> <!--Loading Mathjax--> is coloured with r <!--mathContainer--> <!--Loading Mathjax--> colours, there is a monochromatic set A′⊂B <!--mathContainer--> <!--Loading Mathjax--> which is congruent to A <!--mathContainer--> <!--Loading Mathjax--> . We prove that sets of diameter 1 with circumradius larger than <!--mathContainer--> <!--Loading Mathjax--> are not diameter-Ramsey. In particular, we obtain that triangles with an angle larger than 135° are not diameter-Ramsey, improving a result of Frankl, Pach, Reiher and Rödl. Furthermore, we deduce that there are simplices which are almost regular but not diameter-Ramsey.