Questions tagged [ramsey-theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
37
votes
6answers
3k views

Grid $k$-coloring without monochromatic rectangles

Update: The obstruction set (i.e. the NxM "barrier" between colorable and uncolorable grid sizes) for all monochromatic-rectangle-free 4-colorings is now known. Anyone feel up to trying 5-colorings? ;...
14
votes
2answers
2k views

Application of Ramsey Numbers

The definition of Ramsey numbers is the following: Let $R(a,b)$ be a positive number such that every graph of order at least $R(a,b)$ contains either a clique on $a$ vertices or a stable set on $b$ ...
13
votes
1answer
414 views

Ramsey's theorem for collections of sets

While exploring different techniques of proving lower bounds for distributed algorithms, it occurred to me that the following variant of Ramsey's theorem might have applications – if it happens to be ...
9
votes
2answers
524 views

Extensions of Ramsey's theorem: monochromatic but diverse

As a follow-up of my previous question, which was resolved by Hsien-Chih Chang, here is another attempt to find an appropriate generalisation of Ramsey's theorem. (You don't need to read the previous ...