# Tag Info

## New answers tagged ramsey-theory

### $n^2$-Grid $3n$-Coloring Game: Can we color a n-square grid with 3n colors s. t. we can't select n colors to get an histogram with $\Theta(n^2)$ area?

In order for Bob to win, he needs that at least $\delta n$ columns have values at least $\delta n$ each. So Alice just needs to shuffle the colors to prevent this. In other words, we need $n$ subsets ...
• 18.6k
One cannot arrange 5 points in that manner, even if the coordinates are allowed to be any real numbers. Indeed, assume that the 5 points are $(x_n,y_n)$ with $x_1\leq\dotsb\leq x_5$. By the Erdős-...