Department of
Applied
Mathematics

on Ramsey theory

Gabor Hegedus

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