<p>SDPs usually provide relaxations, so for a minimization problem you'll get a lower bound. The Lovasz theta function does provide such a lower bound on chromatic number (see <a href="http://en.wikipedia.org/wiki/Lov%C3%A1sz_number#Lov.C3.A1sz_.22sandwich_theorem.22">wiki</a>). Upper bounds can be provided by rounding schemes (constructive or otherwise). In general, if you have an upper bound $U$ on the integrality gap of the SDP, you can scale the objective of the SDP by $U$ and you'll get an upper bound as well. However, there <a href="http://authors.library.caltech.edu/27189/1/FEIsiamjc04.pdf">exist graphs</a> for which the Lovasz theta gives a lowerbound of $k = O(1)$ and the chromatic number is at least $n^{1 - 2/k}$. There is some <a href="http://www.cs.princeton.edu/~rongge/LasserreColoring.pdf">hope</a> that higher levels of the Lasserre hierarchy can give stronger relaxations. However, notice that chromatic number is  hard to approximate within $n^{1 - \epsilon}$ (see <a href="http://www.computer.org/portal/web/csdl/doi/10.1109/SFCS.1996.548522">this</a>) in general (i.e. if you're not just interested in the promise problem where the yes instance has constant chromatic number). So, for any SDP, integrality gaps better than $n^{1-\epsilon}$ will either be restricted to cases where the SDP relaxation has  constant value or will be nonconstructive (i.e. superpolynomial time rounding or superpolynomial size relaxation), unless P=NP.</p>

CC BY-SA 3.0
2011-12-23T20:13:33.183Z
very good answer. almost what I am looking for. The notion of integrality gap between the lower bound for chromatic number as provided by SDP and the correct chromatic number is new to me. Is there a reference that provides more details on the study of the integrality gap? Moreover the graphs I am looking at are product graphs. Are there any work on integrality gap for sdps in relation to the chrmatic number?
v s
CC BY-SA 3.0
2011-12-23T22:10:03.303Z
in the Laserre hierarchies paper (http://www.cs.princeton.edu/~rongge/LasserreColoring.pdf) there are some references for integrality gap results: look at references 14, and 15. Also Mario Szegedy showed the Lovasz theta has integrality gap $n^{1-\epsilon}$ w.r.t. independence number if and only if it has integrality gap $n^{1-\epsilon}$ w.r.t. the chromatic number (http://www.cs.rutgers.edu/~szegedy/PUBLICATIONS/theta.ps). Alon and Kahale show an integrality gap of $n^{1-\epsilon}$ for any $\epsilon$ for Lovasz theta w.r.t. independent set. I am not an expert, follow refs in these papers.
Sasho Nikolov
CC BY-SA 3.0
2011-12-23T22:18:34.180Z
about product graphs: the Lovasz theta behaves very nicely with tensor products of graphs. this might be a way to amplify gaps, but i don't know much about the existing integrality gap constructions and i am not sure if they work this way.
Sasho Nikolov
CC BY-SA 3.0
2011-12-23T19:08:37.017Z
2011-12-24T10:53:43.813Z
2011-12-24T10:53:43.813Z
Sasho Nikolov
<p>Are there any references for finding non-trivial upper bounds to chromatic number using semidefinite programming?</p>

CC BY-SA 3.0
2011-12-23T07:08:42.910Z
"outer bounds" ? also, are you referring to the Lovasz theta function ?
Suresh Venkat
CC BY-SA 3.0
2011-12-23T15:50:13.720Z
@Suresh: Here by outer bound, I imply upper bound and by inner bound, I imply lower bound. I thought Lovasz theta is only for outer bounding the independence number? Would it apply to chromatic number as well? Since chromatic number is implicitly a minimal number under some constraints, I am curious if there are any Lovasz type outer bounds to chromatic number and Lovasz type inner bounds for independence number as well?
v s
CC BY-SA 3.0
2011-12-23T16:15:50.260Z
You might want to edit to use the more standard terminology ? (at least standard in algorithms)
Suresh Venkat
CC BY-SA 3.0
2011-12-23T16:39:45.883Z
@SureshVenkat done
v s
<graph-theory><co.combinatorics><semidefinite-programming>
SDP and chromatic number upper bounds
v s
# SDP and chromatic number upper bounds

(Asked by: username_0 on 2011-12-23)

Are there any references for finding non-trivial upper bounds to chromatic number using semidefinite programming?

**Tags:** graph-theory, co.combinatorics, semidefinite-programming
> **Comments:**
> **username_1**: "outer bounds" ? also, are you referring to the Lovasz theta function ?  
> **username_0**: @Suresh: Here by outer bound, I imply upper bound and by inner bound, I imply lower bound. I thought Lovasz theta is only for outer bounding the independence number? Would it apply to chromatic number as well? Since chromatic number is implicitly a minimal number under some constraints, I am curious if there are any Lovasz type outer bounds to chromatic number and Lovasz type inner bounds for independence number as well?  
> **username_1**: You might want to edit to use the more standard terminology ? (at least standard in algorithms)  
> **username_0**: @SureshVenkat done  

---

## 1 answers

### Answer by username_2 on 2011-12-23. Score: 13 | Accepted answer

SDPs usually provide relaxations, so for a minimization problem you'll get a lower bound. The Lovasz theta function does provide such a lower bound on chromatic number (see [wiki](http://en.wikipedia.org/wiki/Lov%C3%A1sz_number#Lov.C3.A1sz_.22sandwich_theorem.22)). Upper bounds can be provided by rounding schemes (constructive or otherwise). In general, if you have an upper bound $U$ on the integrality gap of the SDP, you can scale the objective of the SDP by $U$ and you'll get an upper bound as well. However, there [exist graphs](http://authors.library.caltech.edu/27189/1/FEIsiamjc04.pdf) for which the Lovasz theta gives a lowerbound of $k = O(1)$ and the chromatic number is at least $n^{1 - 2/k}$. There is some [hope](http://www.cs.princeton.edu/~rongge/LasserreColoring.pdf) that higher levels of the Lasserre hierarchy can give stronger relaxations. However, notice that chromatic number is hard to approximate within $n^{1 - \epsilon}$ (see [this](http://www.computer.org/portal/web/csdl/doi/10.1109/SFCS.1996.548522)) in general (i.e. if you're not just interested in the promise problem where the yes instance has constant chromatic number). So, for any SDP, integrality gaps better than $n^{1-\epsilon}$ will either be restricted to cases where the SDP relaxation has constant value or will be nonconstructive (i.e. superpolynomial time rounding or superpolynomial size relaxation), unless P=NP.

> **Comments:**
> **username_0**: very good answer. almost what I am looking for. The notion of integrality gap between the lower bound for chromatic number as provided by SDP and the correct chromatic number is new to me. Is there a reference that provides more details on the study of the integrality gap? Moreover the graphs I am looking at are product graphs. Are there any work on integrality gap for sdps in relation to the chrmatic number?  
> **username_2**: in the Laserre hierarchies paper (http://www.cs.princeton.edu/~rongge/LasserreColoring.pdf) there are some references for integrality gap results: look at references 14, and 15. Also Mario Szegedy showed the Lovasz theta has integrality gap $n^{1-\epsilon}$ w.r.t. independence number if and only if it has integrality gap $n^{1-\epsilon}$ w.r.t. the chromatic number (http://www.cs.rutgers.edu/~szegedy/PUBLICATIONS/theta.ps). Alon and Kahale show an integrality gap of $n^{1-\epsilon}$ for any $\epsilon$ for Lovasz theta w.r.t. independent set. I am not an expert, follow refs in these papers.  
> **username_2**: about product graphs: the Lovasz theta behaves very nicely with tensor products of graphs. this might be a way to amplify gaps, but i don't know much about the existing integrality gap constructions and i am not sure if they work this way.  

---

