TR-2013-09

An extension of Lehman's theorem and ideal set functions

Tamás Király, Júlia Pap

Published in:
Discrete Applied Mathematics, Volume 209, 2016, Pages 251-263. DOI link



Abstract

Lehman's theorem on the structure of minimally nonideal clutters is a fundamental result in polyhedral combinatorics. One approach to extending it has been to give a common generalization with the characterization of minimally imperfect clutters [Sebo 1998; Gasparyan, Preissmann, Sebo 2003]. We give a new generalization of this kind, which combines two types of covering inequalities and works well with the natural definition of minors. We also show how to extend the notion of idealness to unit-increasing set functions, in a way that is compatible with minors and blocking operations.


Older versions:

Bibtex entry:

@techreport{egres-13-09,
AUTHOR = {Kir{\'a}ly, Tam{\'a}s and Pap, J{\'u}lia},
TITLE = {An extension of Lehman's theorem and ideal set functions},
NOTE= {{\tt egres.elte.hu}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2013},
NUMBER = {TR-2013-09}
}


Last modification: 21.3.2024. Please email your comments to Tamás Király!