This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Chen, X. Articles by Zang, W. Search for Related Content

A Characterization of Box-Mengerian Matroid Ports

Institute of Applied Mathematics, Chinese Academy of Sciences, Beijing 100190, China
Mathematics Department, Louisiana State University, Baton Rouge, Louisiana, USA
Department of Mathematics, The University of Hong Kong, Hong Kong, China
xchen{at}amss.ac.cn
ding{at}math.lsu.edu
wzang{at}maths.hku.hk

Let M be a matroid on E{l}, where l E is a distinguished element of M. The l-port of M is the set = {P: P E with P{l} a circuit of M}. Let A be the -E incidence matrix. Let U_{2, 4} be the uniform matroid on four elements of rank two, let F₇ be the Fano matroid, let F₇* be the dual of F₇, and let F₇⁺ be the unique series extension of F₇. In this paper, we prove that the system Ax1, x0 is box-totally dual integral (box-TDI) if and only if M has no U_{2, 4}-minor using l, no F₇*-minor using l, and no F₇⁺-minor using l as a series element. Our characterization yields a number of interesting results in combinatorial optimization.

Key Words: binary clutter; binary matroid; regular matroid; box-total dual integrality
History: Received: October 30, 2006; revision received: October 17, 2007;