The minimum number of edges in graphs with prescribed paths

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=220(m), then C(m,n,K)= H/log H + 0(H/log H), 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. © 1979 Springer-Verlag New York Inc.