Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

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

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

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

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