# Noon lecture

On 01.06.2006 at 12:20 in S5, there is the following noon lecture:

# on Ramsey theory

## Abstract

In this talk I give a very simple algorithm for the $2$-coloring of an arbitrary $r$-uniform hypergraph $\cH$ with at most $|\cH|\cdot 2^{1-r}$ monochromatic edges. This yields also to a simple constructive method to color a graph on $2^{\frac{k}{2}}$ vertices without homogeneous complete subgraph $K_k$.

In the second part of the lecture I give a simple construction of explicit Ramsey graphs which shows that $R(2^{\lfloor n/2 \rfloor},n)>2^{n-1}$.

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010