Lower bound on the size-Ramsey number of tight paths

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)$.

Keywords

size-Ramsey, Ramsey theory, tight paths, hypergraphs

2010 Mathematics Subject Classification

05D10

Full Text (PDF format)

Received 27 October 2021

Published 28 December 2022