The minimum number of edges in graphs with prescribed paths

Abstract

LetM be anm-by-n matrix with entries in {0,1,⋯,K}. LetC(M) denote the minimum possible number of edges in a directed graph in which (1) there arem distinguished vertices calledinputs, andn other distinguished vertices calledoutputs; (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 thei-th input to thej-th output is equal to the (i,j)-th entry ofM. LetC(m,n,K) denote the maximum ofC(M) over allm-by-n matricesM with entries in {0,1,⋯,K}. We assume (without loss of generality) thatm ≥n, and show that ifm=(K+1)⁰⁽ⁿ⁾ andK=2^{2 0(m)}, thenC(m,n,K)= H/logH + 0(H/logH), whereH=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.