Mediated digraphs and quantum nonlocality (Q2565849)

A digraph \(D(V, A)\) is mediated if for each pair \(xy\) of distinct vertices in the vertex set \(V\), either \(xy\) or \(yx\) is in the arc set \(A\) or there is a vertex \(z\) such that both \(xz\) and \(yz\) are in \(A\). Denote by \(I(D)\) the maximum in-degree of a vertex in \(D\). The \(n\)th mediation number \(m(n)\) is the minimum of \(I(D)\) over all mediated digraphs on \(n\) vertices. The paper gives a lower bound \(f(n)\) for \(m(n)\) and determines infinite sequences of values of \(n\) for which \(m(n) = f(n)\) and \(m(n)\) is greater than \(f(n)\), respectively. Finally, it gives upper bounds for \(m(n)\).