The Minimum Number of Edges in Graphs with Prescribed Paths

Document Type



Mathematics (HMC)

Publication Date



Let M be an m-by-n matrix with entries in {0,1,⋯,K}. Let C(M) denote the minimum possible number of edges in a directed graph in which (1) there are m distinguished vertices called inputs, and n other distinguished vertices called outputs; (2) there is no directed path from an input to another input, from an output to another output, or from an output to an input; and (3) for all 1 ≤im and 1 ≤jn, the number of directed paths from the i-th input to the j-th output is equal to the (i,j)-th entry of M. Let C(m,n,K) denote the maximum of C(M) over all m-by-n matrices M with entries in {0,1,⋯,K}. We assume (without loss of generality) that mn, and show that if m=(K+1) 0(n) and K=22 0(m) , then C(m,n,K)= H/logH + 0(H/logH), where H=mnlog(K + 1) and all logarithms have base 2. The proof involves an interesting problem of Diophantine approximation, which is solved by means of an unusual continued fraction expansion.

Rights Information

© 1978 Springer-Verlag

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.