aussois_header.png

A characterization of unimodular hypergraphs with disjoint hyperedges
Marco Caoduro  1  , Meike Neuwohner  2@  , Joseph Paat  1  
1 : Sauder School of Business [British Columbia]
2 : Department of Mathematics London School of Economics

Grossman et al. show that the subdeterminants of the incidence ma-
trix of a graph can be characterized using the graph's odd cycle packing
number. In particular, a graph's incidence matrix is totally unimodular
if and only if the graph is bipartite. We extend the characterization of
total unimodularity to disjoint hypergraphs, i.e., hypergraphs whose hy-
peredges of size at least four are pairwise disjoint. Disjoint hypergraphs
interpolate between graphs and hypergraphs, which correspond to arbi-
trary {0, 1}-matrices. We prove that total unimodularity for disjoint hy-
pergraphs is equivalent to forbidding both odd cycles and a structure we
call an “odd tree house”. Our result extends to disjoint directed hyper-
graphs, i.e., those whose incidence matrices allow for {0, ±1}-entries. As
a corollary, we resolve a conjecture on almost totally unimodular matri-
ces, formulated by Padberg (1988) and Cornuéjols & Zuluaga (2000), in
the special case where columns with at least four non-zero elements have
pairwise disjoint supports.



  • Poster
Personnes connectées : 2 Vie privée | Accessibilité
Chargement...