×

Enumeration of integer solutions to linear inequalities defined by digraphs. (English) Zbl 1170.05007

Beck, Matthias (ed.) et al., Integer points in polyhedra—geometry, number theory, algebra, optimization, statistics. Proceedings of the AMS-IMS-SIAM joint summer research conference, Snowbird, UT, USA, June 11–15, 2006. Providence, RI: American Mathematical Society (AMS) (ISBN 978-0-8218-4173-0/pbk). Contemporary Mathematics 452, 79-91 (2008).
The authors consider solutions \((\lambda_1,\dots,\lambda_n)\) to a system \(C\) of inequalities in which every constraint is of the form \(\lambda_i\geq\lambda_j\) (or \(\lambda_i> \lambda_j\)). In this case, \(C\) can be modelled by a directed graph (digraph) in which the vertices are labeled \(1,\dots, n\) and there is an edge (or strict edge) from \(i\) to \(j\) if \(C\) contains the constraints \(\lambda_i\geq \lambda_j\) (or \(\lambda_i< \lambda_j\)). Many familiar systems can be modelled in this way, including ordinary partitions and compositions, plane partitions, monotone triangles, and plane partition triangles and generalizations.
For the entire collection see [Zbl 1135.52001].

MSC:

05A15 Exact enumeration problems, generating functions
05C20 Directed graphs (digraphs), tournaments
05A17 Combinatorial aspects of partitions of integers
11P21 Lattice points in specified regions
15A39 Linear inequalities of matrices
11D75 Diophantine inequalities

Software:

Omega
PDFBibTeX XMLCite