Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|cite|improve this question
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. – Eden Harder Jan 15 '14 at 0:48

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.