Questions tagged [ramsey-theory]
The ramsey-theory tag has no usage guidance.
13 questions
2
votes
0
answers
94
views
Complexity of (Graph) Ramsey Theorem in Sum-of-Squares Proof System
(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 ...
- 223
6
votes
0
answers
121
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$ ...
- 1,002
2
votes
1
answer
281
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 ...
- 13.3k
1
vote
0
answers
169
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 ...
- 13.3k
11
votes
0
answers
148
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$.
...
- 14.2k
8
votes
1
answer
182
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 ...
- 1,927
13
votes
0
answers
530
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 ...
- 10.3k
14
votes
2
answers
3k
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$ ...
- 944
2
votes
1
answer
184
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 ...
- 2,228
6
votes
0
answers
208
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-...
- 549
8
votes
2
answers
541
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 ...
- 11.6k
13
votes
1
answer
431
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 ...
- 11.6k
38
votes
6
answers
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? ;...
- 6,041