Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [ramsey-theory]

The tag has no usage guidance.

6
votes
0answers
89 views

Ramsey number for path in a colored tournament

I am looking about the following Ramseyish theorem with additional structure on tournament (see [1]). For all number of colors $k$, there exists $n=T(k)$ such that all tournaments of size $n$ ...
2
votes
1answer
245 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 ...
1
vote
0answers
147 views

Ramsey theory through semidefinite programming

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 ...
10
votes
0answers
141 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$. ...
8
votes
1answer
146 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 ...
13
votes
0answers
462 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 ...
13
votes
2answers
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$ ...
2
votes
1answer
177 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 ...
6
votes
0answers
197 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-...
9
votes
2answers
496 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 ...
13
votes
1answer
384 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 ...
37
votes
6answers
2k 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? ;...