7
$\begingroup$

Quantum motivation

Noncontextuality inequalities (and in particular Bell inequalities) can be mapped into graphs, in such a way that its relevant properties can be calculated via some simple graph-theoretical functions. In particular, the maximal quantum violation of a noncontextuality inequality is upperbounded by the Lovász function of its graph.

A family of inequalities that interests myself particularly is represented by the Möbius ladder; I was unable to find its Lovász function in the literature, but from physical and mathematical grounds we managed to prove that $$\frac{n}{2}\bigg(1+\cos\frac{\pi}{n}\bigg) \le\vartheta(M_{2n}) \le \frac{n\big(2\cos(\pi/n)+1\big)}{2+\cos(\pi/n)}.$$ Note that both bounds coincide in the asymptotic limit. Furthermore, my physical intuition claims that the function is always equal to this lower bound. I cannot prove it, however.

Quantum-free question

Let $M_{2n}$ be the Möbius ladder graph. I conjecture ts Lovász function to be

$$\vartheta(M_{2n}) = \frac{n}{2}\bigg(1+\cos\frac{\pi}{n}\bigg).$$ But I can not prove this. I hope that this problem would be easy to a graph-theoretician, or even buried in the literature somewhere. Anybody knows?

$\endgroup$
1
  • $\begingroup$ Since the Möbius ladder is isomorphic to the circulant graph $Ci_{2n}(1,n)$, we can think about $Ci_{2n}(1,n)$. But I have no idea too. $\endgroup$ Jan 15, 2014 at 0:48

1 Answer 1

1
$\begingroup$

Now, 9 years later, this conjecture has been proven by Bharti et al. (one of the authors is Adán Cabello, who was in the paper that originally posed the conjecture).

The technique used was semidefinite programming (SDP) duality: computing the Lovász function is an SDP, and as all SDPs it has a dual SDP that upperbounds the solution of the primal SDP. They managed to find a feasible solution of the dual for all even $n$ that coincides with the already known lower bound that came from a feasible solution of the primal, proving that both solutions are optimal and give the Lovász function.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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