7
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ "outer bounds" ? also, are you referring to the Lovasz theta function ? $\endgroup$ – Suresh Venkat Dec 23 '11 at 7:08
  • $\begingroup$ @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? $\endgroup$ – v s Dec 23 '11 at 15:50
  • $\begingroup$ You might want to edit to use the more standard terminology ? (at least standard in algorithms) $\endgroup$ – Suresh Venkat Dec 23 '11 at 16:15
  • $\begingroup$ @SureshVenkat done $\endgroup$ – v s Dec 23 '11 at 16:39
13
$\begingroup$

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). 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 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 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) 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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – v s Dec 23 '11 at 20:13
  • 2
    $\begingroup$ in the Laserre hierarchies paper (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 (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. $\endgroup$ – Sasho Nikolov Dec 23 '11 at 22:10
  • $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Dec 23 '11 at 22:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.