Seminario de Grafos, Seminarios

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.

 

Comparte en:

Otras noticias