Journal of Combinatorics

Volume 14 (2023)

Number 2

Lower bound on the size-Ramsey number of tight paths

Pages: 271 – 279



Christian Winter (University of Hamburg, Germany; and Karlsruhe Institute of Technology, Karlsruhe, Germany)


The size-Ramsey number $\hat{R}^{(k)} (\mathcal{H})$ of a $k$-uniform hypergraph $\mathcal{H}$ is the minimum number of edges in a k-uniform hypergraph $\mathcal{G}$ with the property that every ‘2-edge coloring’ of $\mathcal{G}$ contains a monochromatic copy of $\mathcal{H}$. For $k \geq 2$ and $n \in \mathbb{N}$, a $k$-uniform tight path on $n$ vertices $\mathcal{P}^{(k)}_n$ is defined as a $k$-uniform hypergraph on $n$ vertices for which there is an ordering of its vertices such that the edges are all sets of $k$ consecutive vertices with respect to this order.

We prove a lower bound on the size-Ramsey number of $k$-uniform tight paths, which is, considered assymptotically in both the uniformity $k$ and the number of vertices $n, \hat{R}^{(k)} (\mathcal{P}^{(k)}_n) = \Omega (\operatorname{log}(k)n)$.


size-Ramsey, Ramsey theory, tight paths, hypergraphs

2010 Mathematics Subject Classification


Received 27 October 2021

Published 28 December 2022