The Minimum Number of Edges in Graphs with Prescribed Paths
Document Type
Article
Department
Mathematics (HMC)
Publication Date
1978
Abstract
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 ≤i ≤m and 1 ≤j ≤n, 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 m ≥n, 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
DOI
10.1007/BF01776581
Recommended Citation
Pippenger, N. "The Minimum Number of Edges in Graphs with Prescribed Paths", Math. Sys. Theory, 12 (1979), 325-346. doi: 10.1007/BF01776581
