Cyclic Inclusion-Exclusion

DOI10.1137/140991364MaRDI QIDQ3455243zbMATH OpenOpenAlexFDO

Authors Valentin Féray

Publication date 4 December 2015

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.1772

zbMATH Keywords

partially ordered setquasi-symmetric functions

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Symmetric functions and generalizations (05E05) Combinatorics of partially ordered sets (06A07)

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

Recommendations

• Circular inclusion
• Cyclic derangements
• Inclusion-exclusion redux
• Cyclic inclusion-exclusion and the kernel of \(P\)-partitions
• Symmetric inclusion-exclusion
• scientific article; zbMATH DE number 1270967
• Cyclic graphs
• On cycle sequences

Cites work

• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 1111371 (Why is no real title available?)
• scientific article; zbMATH DE number 1974576 (Why is no real title available?)
• scientific article; zbMATH DE number 3895079 (Why is no real title available?)
• A Note on Solid Partitions
• A matroid-friendly basis for the quasisymmetric functions
• A rational-function identity related to the Murnaghan-Nakayama formula for the characters of \(S_ n\)
• An extension of MacMahon's equidistribution theorem to ordered multiset partitions
• An introduction to quasisymmetric Schur functions. Hopf algebras, quasisymmetric functions, and Young composition tableaux.
• Application of graph combinatorics to rational identities of type A
• Combinatorial interpretation and positivity of Kerov's character polynomials
• Expander graphs and their applications
• Explicit combinatorial interpretation of Kerov character polynomials as numbers of permutation factorizations
• Monoidal functors, species and Hopf algebras
• On posets and Hopf algebras
• Ordered structures and partitions
• Super quasi-symmetric functions via Young diagrams
• THE HOPF ALGEBRAS OF SYMMETRIC FUNCTIONS AND QUASI-SYMMETRIC FUNCTIONS IN NON-COMMUTATIVE VARIABLES ARE FREE AND CO-FREE
• The On-Line Encyclopedia of Integer Sequences
• The descent set and connectivity set of a permutation
• Zonal polynomials via Stanley's coordinates and free cumulants

Cited in

(4)

• The kernel of chromatic quasisymmetric functions on graphs and nestohedra
• Positivity among \(P\)-partition generating functions
• The kernel of chromatic quasisymmetric functions on graphs and hypergraphic polytopes
• Cyclic inclusion-exclusion and the kernel of \(P\)-partitions

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Cyclic Inclusion-Exclusion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3455243)