# Questions tagged [ramsey-theory]

Use for questions in Ramsey Theory, i.e. regarding how large a structure must be before it is guaranteed to have a certain property. Please be especially careful not to ask open questions in this tag.

663 questions
Filter by
Sorted by
Tagged with
1 vote
93 views

### What does $[S]^k$ mean if $S$ is a set?

I am trying to understand a statement of Ramsey's theorem quoted by Karen R. Johannson in "Variations on a theorem by van der Waerden". She states, For every $k, m, r \in \mathbb{Z}^+$ there ...
71 views

### How many ways are there to $2$-Color an $N$ by $N$ Grid such that there is at least one $3$ by $3$ Square?

Given an $N$ by $N$ grid, how many ways are there to $2$-color the grid such that there is at least one $3$ by $3$ grid with all its four corners having the same color? Initially I had this expression ...
29 views

### Whether we can use the dual Ramsey theorem to prove the finite Ramsey theorem?

The dual Ramsey theorem was firstly proved by Graham and Rothschild in 1971, it said that for the natural number $d$,$k$,$l\in\omega$, there exists a natural number $m$ such that for each $d$-...
98 views

### Maximum number of colors for embedding all colored perfect matchings in the complete graph

For given $n>1$ I'm looking for the maximum number $k$ of colors such that there exists a $k$-coloring of the edges of the complete graph on $2n$ vertices with the property that a copy of every ...
• 3,568
1 vote
62 views

### Existence of Identically-2-colored Equidistant Points on the Integers

I was wondering if every 2-coloring of the integer set would result in some number of equidistant (equally-spaced) points. I proved that there will always be 3 equally-spaced points of the same color, ...
24 views

### Bound on the number of monochromatic $K_i$ in a $K_k$ free colored graph

I have a question that I need help with. Suppose you have some integers $k,q$ and $N$ and a fixed q-coloring on the edges of $K_N$ such that it contains no monochromatic $K_k$. Is there a nice way to ...
47 views

• 20.2k
96 views

### Every set of size $2^n-1$ has a subset of size $2^{n-1}$ that sums to a multiple of $n$

Is the following statement true? If so, how can it be proved? Every set of $2^n-1$ positive integers, $n\in\{1,2,\dots\}$, has a subset of size $2^{n-1}$ that sums to a multiple of $n$. An attempt ...
• 11.4k