The V á mos Network

The well-studied Vámos matroid has provided a wealth of interesting theoretical results in matroid theory. We use the Vámos matroid to construct a new network, which we call the Vámos network. We then exploit the Vámos network to answer in the negative the open question as to whether Shannon-type information inequalities are in general sufficient for computing network coding capacities. To accomplish this, we first determine the smallest coding capacity upper bound that can be obtained for the Váamos network using only Shannon-type information inequalities. Then, we prove that a smaller capacity upper bound for the Vámos network can be obtained by using a non-Shannon-type information inequality discovered in 1998 by Zhang and Yeung. This is the first published application of a non-Shannon-type inequality to network coding. Finally, we demonstrate that one can compute the exact routing capacity and linear coding capacity of the Vámos network.