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

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.