Header

UZH-Logo

Maintenance Infos

Cyclic inclusion-exclusion


Féray, Valentin (2015). Cyclic inclusion-exclusion. SIAM Journal on Discrete Mathematics, 29(4):2284-2311.

Abstract

Following the lead of Stanley and Gessel, we consider a linear map which associates to an acyclic directed graph (or a poset) a quasi-symmetric function. The latter is naturally defined as a multivariate generating series of nondecreasing functions on the graph. We describe the kernel of this linear map by using a simple combinatorial operation that we call cyclic inclusion-exclusion. Our result also holds for the natural noncommutative analogue and for the commutative and noncommutative restrictions to bipartite graphs. An application to the theory of Kerov character polynomials is given.

Abstract

Following the lead of Stanley and Gessel, we consider a linear map which associates to an acyclic directed graph (or a poset) a quasi-symmetric function. The latter is naturally defined as a multivariate generating series of nondecreasing functions on the graph. We describe the kernel of this linear map by using a simple combinatorial operation that we call cyclic inclusion-exclusion. Our result also holds for the natural noncommutative analogue and for the commutative and noncommutative restrictions to bipartite graphs. An application to the theory of Kerov character polynomials is given.

Statistics

Altmetrics

Downloads

0 downloads since deposited on 11 Feb 2016
0 downloads since 12 months

Additional indexing

Item Type:Journal Article, refereed, original work
Communities & Collections:07 Faculty of Science > Institute of Mathematics
Dewey Decimal Classification:510 Mathematics
Language:English
Date:24 November 2015
Deposited On:11 Feb 2016 07:57
Last Modified:08 Dec 2017 18:53
Publisher:Society for Industrial and Applied Mathematics
ISSN:0895-4801
Publisher DOI:https://doi.org/10.1137/140991364

Download

Content: Published Version
Language: English
Filetype: PDF - Registered users only
Size: 346kB
View at publisher