<p>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$.
The big open problem is to prove or disprove that there is an $f\in$ RAMSEY COLORING such that $f\in FP$.
Is there anything known about smaller complexity classes, like an $f\in$ RAMSEY COLORING such that $f\in NC$ or $f\in LOGSPACE$?</p>

<p>I suppose $LOGSPACE$ is out of reach, but $f\notin AC_0$ seems to be trivial.</p>

CC BY-SA 3.0
2017-12-20T18:29:28.523Z
Are you asking for unconditional lower bounds? As I think you're already aware, we have very few proof techniques for unconditional lower bounds, aside from diagonalization (which would seem not to work here, unless you know of some universality result for Ramsey coloring) and for small classes like $\mathsf{AC}^0$ (many, starting with Furst-Saxe-Sipser) or $\mathsf{ACC}^0$ (Williams, although that also used diagonalization). Or if you'd be interested in conditional lower bounds you could ask more specifically something like: is RAMSEY COLORING $\mathsf{NL}$-hard? Is it $\mathsf{DET}$-hard?
Joshua Grochow
CC BY-SA 3.0
2017-12-21T05:38:42.480Z
@Joshua Now being 3 years wiser, I agree these that these seem to be better questions.
domotorp
<cc.complexity-theory><graph-theory><co.combinatorics><ramsey-theory>
Is RAMSEY COLORING in $NC$?
domotorp
# Is RAMSEY COLORING in $NC$?

(Asked by: username_0 on 2014-08-02)

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$.
The big open problem is to prove or disprove that there is an $f\in$ RAMSEY COLORING such that $f\in FP$.
Is there anything known about smaller complexity classes, like an $f\in$ RAMSEY COLORING such that $f\in NC$ or $f\in LOGSPACE$?

I suppose $LOGSPACE$ is out of reach, but $f\notin AC\_0$ seems to be trivial.

**Tags:** cc.complexity-theory, graph-theory, co.combinatorics, ramsey-theory
> **Comments:**
> **username_1**: Are you asking for unconditional lower bounds? As I think you're already aware, we have very few proof techniques for unconditional lower bounds, aside from diagonalization (which would seem not to work here, unless you know of some universality result for Ramsey coloring) and for small classes like $\mathsf{AC}^0$ (many, starting with Furst-Saxe-Sipser) or $\mathsf{ACC}^0$ (Williams, although that also used diagonalization). Or if you'd be interested in conditional lower bounds you could ask more specifically something like: is RAMSEY COLORING $\mathsf{NL}$-hard? Is it $\mathsf{DET}$-hard?  
> **username_0**: @Joshua Now being 3 years wiser, I agree these that these seem to be better questions.  

---

## 0 answers

