Graph Theory Seminar “Ramsey numbers of expansion hypertrees”

Abstract: Given a $k$-uniform hypergraph $H$, the Ramsey number $R(H)$ is the smallest $N$ such that every $2$-colouring of the edges of $K_N^{(k)}$ contains a monochromatic copy of $H$. For graphs, Burr gave two constructions bounding $R(T)$ from below for a tree $T$, and his formula is now known to be exact for trees of small maximum degree. In the hypergraph setting, almost nothing is known beyond loose paths and cycles.

We study $R(T^{(k)})$, where $T^{(k)}$ is the $k$-expansion of a tree $T$, obtained by adding $k-2$ new vertices to each edge. We show that for bounded-degree trees the Ramsey number is at most $(1+\eta)\frac{1}{2}(2k-1)n$, and we prove a general lower bound $R(H) \geq |V(H)| + \tau(H) – 1$ for connected $k$-graphs $H$, where $\tau$ is the vertex cover number. These bounds are asymptotically tight for loose paths. In this talk, we will see how Burr's constructions generalise to the hypergraph setting, what the resulting lower bound looks like for expansions, and discuss the conjectures this work suggests.

Speaker: Vicente Sandoval (DIM, U. Chile)