Mediated digraphs and quantum nonlocality - Gutin,G; Jones,N; Rafiey,A; Severini,S; Yeo,A (Discrete Applied Mathematics, 2005)
A digraph D = ( V , A ) is mediated if for each pair x , y of distinct vertices of D , either xy ∈ A or yx ∈ A or there is a vertex z such that both xz , yz ∈ A . For a digraph D , Δ - ( D ) is the maximum in-degree of a vertex in D . The n th 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.