Mediated digraphs and quantum nonlocality

Abstract

A digraph D=(V,A) is mediated if for each pair x,y of distinct vertices of D, either xyA or yxA or there is a vertex z such that both xz,yzA. For a digraph D, Δ-(D) is the maximum in-degree of a vertex in D. The nth mediation number μ(n) is the minimum of Δ-(D) over all mediated digraphs on n vertices. Mediated digraphs and μ(n) are of interest in the study of quantum nonlocality.

We obtain a lower bound f(n) for μ(n) and determine infinite sequences of values of n for which μ(n)=f(n) and μ(n)>f(n), respectively. We derive upper bounds for μ(n) and prove that μ(n)=f(n)(1+o(1)). We conjecture that there is a constant c such that μ(n)f(n)+c. Methods and results of design theory and number theory are used.