A bimonotone linear inequality is a linear inequality with at most two nonzero coefficients that are of opposite signs (if both different from zero). A linear inequality defines a halfspace that is a sublattice of Rn (a subset closed with respect to componentwise maximum and minimum) if and only if it is bimonotone. Veinott has shown that a polyhedron is a sublattice if and only if it can be defined by a finite system of bimonotone linear inequalities, whereas Topkis has shown that every sublattice of Rn (and of more general product lattices) is the solution set of a system of nonlinear bimonotone inequalities. In this paper we prove that a subset of Rn is the solution set of a countable system of bimonotone linear inequalities if and only if it is a closed convex sublattice. Similarly, we note that a subset of Rn is closed and convex if and only if it is the solution set of a countable system of linear inequalities. We also present necessary and/or sufficient conditions for a sublattice to be the intersection of the cartesian product of its projections on the coordinate axes with the solution set of a (possibly infinite) system of bimonotone linear inequalities. We provide explicit constructions of such systems of bimonotone linear inequalities under certain assumptions on the sublattice. We obtain Veinott’s polyhedral representation theorem and a 0–1 version of Birkhoff’s Representation Theorem as corollaries. We also point out a few potential pitfalls regarding properties of sublattices of Rn.

Bimonotone linear inequalitites and sublattices of Rn / M., Queyranne; Tardella, Fabio. - In: LINEAR ALGEBRA AND ITS APPLICATIONS. - ISSN 0024-3795. - STAMPA. - 413:(2006), pp. 100-120. [10.1016/j.laa.2005.08.004]

Bimonotone linear inequalitites and sublattices of Rn

TARDELLA, Fabio
2006

Abstract

A bimonotone linear inequality is a linear inequality with at most two nonzero coefficients that are of opposite signs (if both different from zero). A linear inequality defines a halfspace that is a sublattice of Rn (a subset closed with respect to componentwise maximum and minimum) if and only if it is bimonotone. Veinott has shown that a polyhedron is a sublattice if and only if it can be defined by a finite system of bimonotone linear inequalities, whereas Topkis has shown that every sublattice of Rn (and of more general product lattices) is the solution set of a system of nonlinear bimonotone inequalities. In this paper we prove that a subset of Rn is the solution set of a countable system of bimonotone linear inequalities if and only if it is a closed convex sublattice. Similarly, we note that a subset of Rn is closed and convex if and only if it is the solution set of a countable system of linear inequalities. We also present necessary and/or sufficient conditions for a sublattice to be the intersection of the cartesian product of its projections on the coordinate axes with the solution set of a (possibly infinite) system of bimonotone linear inequalities. We provide explicit constructions of such systems of bimonotone linear inequalities under certain assumptions on the sublattice. We obtain Veinott’s polyhedral representation theorem and a 0–1 version of Birkhoff’s Representation Theorem as corollaries. We also point out a few potential pitfalls regarding properties of sublattices of Rn.
2006
Bimonotone inequalities; Lattice theory; Convex lattice
01 Pubblicazione su rivista::01a Articolo in rivista
Bimonotone linear inequalitites and sublattices of Rn / M., Queyranne; Tardella, Fabio. - In: LINEAR ALGEBRA AND ITS APPLICATIONS. - ISSN 0024-3795. - STAMPA. - 413:(2006), pp. 100-120. [10.1016/j.laa.2005.08.004]
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/17496
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 14
  • ???jsp.display-item.citation.isi??? 9
social impact