Cyclic Inclusion-Exclusion

DOI10.1137/140991364zbMATH Open1351.05225arXiv1410.1772OpenAlexW269766558MaRDI QIDQ3455243FDOQ3455243

Authors: Valentin Féray 

Publication date: 4 December 2015

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

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.

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

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

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)

Cites Work

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

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

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)