[19] Show that there exist labeled graphs on n nodes such that each local routing function must be stored in at least 1 2n log 1 2n − O(n)

bits per node (hence the complete routing scheme requires at least

(n2/2) log 1 2n − O(n2) bits to be stored).

Comments. Source: [H.M. Buhrman, J.H. Hoepman, and P.M.B. Vit´anyi, SIAM J. Comput., 28:4(1999), 1414–1432]. This is also the source for the next four exercises.