# Questions tagged [ramsey-theory]

Branch of combinatorics with the philosophy that 'total disorder is impossible'. For example, Ramsey's theorem asserts that for each $n$, every sufficiently large graph either contains a clique of size $n$ or a stable set of size $n$.

210 questions
Filter by
Sorted by
Tagged with
341 views

• 331
218 views

• 966
1 vote
48 views

### Group graphs and Ramsey Theory. Sub-question 2

This note is a continuation of Group graphs and Ramsey theory. Sub-question 1. Let $\ X\$ be a group, and let $\ c:\binom X2\to C\$ be a two-coloring ($r\$ and $\ g\$ are the two colors). ...
• 4,674
1 vote
97 views

• 203
305 views

### Best known upper bound for the Ramsey function $R(k,x)$

The Ramsey function $R(k,x)$ is defined as the minimal integer $n$ such that any graph on $n$ vertices contains either a clique of size $k$ or an independent set of size $x$. Miklós Ajtai, János ...
• 386
197 views

### Ramsey Numbers for Integers

Erdos defined $f(n)$ to be the minimum $r$ such that there is an $r$-coloring of the positive integers less than $n$, wherein $n$ cannot be written as the sum of distinct monochromatic integers. ...
• 141
174 views

### Graphs with linear Ramsey number for two colors, but super-linear Ramsey number for three colors?

Given a graph $H$, let $R_k(H)$ be the smallest integer $N$ such that in every $k$-coloring of the edges $K_N$ there is a monochromatic copy of $H$ (in other words, $R_k(H)$ is the ordinary $k$-color ...
• 1,626
Reading the proof of the Hales-Jewett theorem the author defines $W_L$ as the set of finite words over some alphabet $L$, $W_{L_v}$ as the set of variable-words over $L$, i.e. finite words over \$L \...