Existence of new inequalities for representable polymatroids

Details Existence of new inequalities for representable polymatroids Existence of new inequalities for representable polymatroids

2009-07-29

arxiv.org/abs/0907.5030v2

Computer Science

Information Theory

Scientific paper

An Ingletonian polymatroid satisfies, in addition to the polymatroid axioms, the inequalities of Ingleton (Combin. Math. Appln., 1971). These inequalities are required for a polymatroid to be representable. It is has been an open question as to whether these inequalities are also sufficient. Representable polymatroids are of interest in their own right. They also have a strong connection to network coding. In particular, the problem of finding the linear network coding capacity region is equivalent to the characterization of all representable, entropic polymatroids. In this paper, we describe a new approach to adhere two polymatroids together to produce a new polymatroid. Using this approach, we can construct a polymatroid that is not inside the minimal closed and convex cone containing all representable polymatroids. This polymatroid is proved to satisfy not only the Ingleton inequalities, but also the recently reported inequalities of Dougherty, Freiling and Zeger. A direct consequence is that these inequalities are not sufficient to characterize representable polymatroids.

Affiliated with

Also associated with

No associations

Rating

Existence of new inequalities for representable polymatroids does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Existence of new inequalities for representable polymatroids, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Existence of new inequalities for representable polymatroids will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-521139