Canonical Ramsey numbers for partite hypergraphs.

Abstract: Ramsey’s theorem states that for sufficiently large n, any r-colouring of the edges of the complete k-uniform hypergraph on n vertices contains a monochromatic copy of the complete k-uniform hypergraph on t vertices. Erdős and Rado generalised this result to an unbounded number of colours. They characterised all canonical colour patterns that are unavoidable in edge colourings of sufficiently large complete hypergraphs. We consider quantitative aspects of this result. For Erdős and Rado’s theorem, both the lower and upper bound on n grow as (k-1)-times iterated exponential polynomials of t. We show that for k-partite k-uniform hypergraphs the upper bound on n grows single exponentially.

Posted on Aug 29, 2025 in Seminario de Grafos, Seminars