## New answers tagged ramsey-theory

0
votes

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

50
votes

Accepted

### Is there a configuration of 5 points on the plane where any two can be covered by an axis aligned rectangle?

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

Top 50 recent answers are included

#### Related Tags

ramsey-theory × 187co.combinatorics × 113

graph-theory × 62

set-theory × 30

reference-request × 29

graph-colorings × 17

additive-combinatorics × 13

nt.number-theory × 10

infinite-combinatorics × 10

lo.logic × 9

extremal-graph-theory × 8

extremal-combinatorics × 6

discrete-geometry × 5

semigroups-and-monoids × 4

ultrafilters × 4

pr.probability × 3

gr.group-theory × 3

mg.metric-geometry × 3

ergodic-theory × 3

descriptive-set-theory × 3

open-problems × 3

permutations × 3

hypergraph × 3

ordinal-numbers × 3

arithmetic-progression × 3