Characterizing integral g-polymatroids
Pritchard conjectures the following[1] about g-polymatroids:
For any polyhedron [math]P[/math] which is not an integral g-polymatroid, there is an integral g-polymatroid [math]Q[/math] such that [math]P \cap Q[/math] is non-integral.
The conjecture was proved by Júlia Pap [2] using a characterization of g-polymatroids by Tomizawa.
Remarks
In the paper introducing g-polymatroids[3], Frank showed that the intersection of any two integral polymatroids is integral. (As usual, a polyhedron is integral if every face contains an integer vector.) Thus, the conjecture is a converse to Frank's theorem.
Since [math]R^n[/math] is a g-polymatroid, the theorem is trivial if P is not integral, since we can take [math]Q=R^n[/math]. Therefore we may assume P is integral, but not a g-polymatroid.
References
- ↑ D. Pritchard. The Hypergraphic Tutte/Nash-Williams Theorem via Integer Decomposition, Total Dual Laminarity, and Power Matroids, EGRES Quick Proof no. 2010-06.
- ↑ J. Pap, A note on generalized polymatroids, EGRES Quick Proof no. 2011-03.
- ↑ A. Frank. Generalized polymatroids. In A. Hajnal, L. Lovász, and V. T. Sós, editors, Finite and Infinite Sets, Vol. I (Eger 1981), volume 37 of Colloq. Math. Soc. János Bolyai, pages 285–294. North-Holland, 1984. Author link.
