# Questions tagged [ramsey-theory]

The tag has no usage guidance.

13 questions
Filter by
Sorted by
Tagged with
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? ;...
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$ ...
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 ...
501 views

### Approximating and bounding Ramsey numbers

Calculating the diagonal Ramsey numbers R(s,s) is hard. There is a famous quote from Joel Spencer: Erdős asks us to imagine an alien force, vastly more powerful than us, landing on Earth and ...
145 views

### Is RAMSEY COLORING in $NC$?

Say that a function $f$ is a RAMSEY COLORING if on unary input $n$, it returns a complete graph on $n$ vertices with its edges colored red and blue without a monochromatic clique of size $10\log n$. ...
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 ...
163 views

### Density of Ramsey Graphs

Suppose we have a graph $G$ with $n$ vertices that contains neither a clique of size $3 \log(n)$ nor an independent set of size $3 \log(n)$ (for example $G(n,0.5)$ satisfies this property with with ...
110 views

### Ramsey number for path in a colored tournament

I am looking about the following Ramseyish theorem with additional structure on tournament (see ). For all number of colors $k$, there exists $n=T(k)$ such that all tournaments of size $n$ ...
206 views

### More elementary proof of coloring theorem for d x d^2 rectangles

The following is known: For all $c$, for all $c$-colorings of $N\times N$ there exists a $d \times d^2$ rectangle ($d \ge 2$) such that all four corners are the same color. The proof uses the Poly-...
180 views

### Decomposing complete graphs into clique-free graphs of certain size

Modified in accordance with Tsuyoshi's comment which seems to generalize. Let $K_{m}$ be a complete graph on $m$ vertices. Is there a way to partition the graphs in to sets of graphs that have no ...
258 views

### Complexity involving connected components of 0/1 matrix

Assume a matrix has one component means we can traverse from a matrix entry $(i,j)$ which is $1$ to any other one by moving step of $(i\pm1,j),(i,j\pm1),(i\pm1,j\pm1)$ where each step you take you ...
(One formulation of) Ramsey's theorem states that any colouring of edges of the complete graph with $4^n$ vertices with two colours will contain a monochromatic clique of size $n$. I am new to proof ...
Could we realize good bounds on Ramsey theoretic problems using semidefinite programming? Example: Is there a good bound on Ramsey numbers $R(r,s)$ from semidefinite programming? Does number of ...