UBC Discrete Math Seminar: Joe Paat

Totally unimodular constraint matrices have been used for decades to model many problems in combinatorial optimization; these matrices are particularly useful as then integer programs can be solved as linear ones. Recent results, in particular one due to Artmann et al., has spurred the study of more general Delta-modular constraint matrices defined to have minors within a fixed range. In this talk, we explore a simple property of Delta-modular matrices: "how many distinct columns they can have?". We give an overview of this question and provide recent results, and in particular we identify some excluded sub matrices that can be used to address this question. Finally, we demonstrate how this column number can be used in integer programming.