Mediated digraphs and quantum nonlocality

DOI10.1016/J.DAM.2005.05.002MaRDI QIDQ2565849zbMATH OpenOpenAlexFDO

Publication date 28 September 2005

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0411653

Combinatorial aspects of block designs (05B05) Directed graphs (digraphs), tournaments (05C20) Quantum measurement theory, state operations, state preparations (81P15)

Abstract: A digraph D=(V,A) is mediated if, for each pair x,y of distinct vertices of D, either xy belongs to A or yx belongs to A or there is a vertex z such that both xz,yz belong to A. For a digraph D, DELTA(D) is the maximum in-degree of a vertex in D. The "nth mediation number" mu(n) is the minimum of DELTA(D) over all mediated digraphs on n vertices. Mediated digraphs and mu(n) are of interest in the study of quantum nonlocality. We obtain a lower bound f(n) for mu(n) and determine infinite sequences of values of n for which mu(n)=f(n) and mu(n)>f(n), respectively. We derive upper bounds for mu(n) and prove that mu(n)=f(n)(1+o(1)). We conjecture that there is a constant c such that mu(n)=<f(n)+c. Methods and results of graph theory, design theory and number theory are used.

Review text

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)\).

Recommendations

Cites work

Cited in

(1)

scientific article; zbMATH DE number 4101246 (Why is no real title available?)

This page was built for publication: Mediated digraphs and quantum nonlocality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2565849)