#### Title

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*=2^{2} ^{0(m) }, then *C(m,n,K)= H*/log*H + 0(H*/log*H*), where* H=mn*log(*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