Decomposition spaces in combinatorics

A decomposition space (also called 2 2 -Segal space) is a simplicial object satisfying an exactness condition weaker than the Segal condition: just as the Segal condition expresses composition, the new condition expresses decomposition. It is a general framework for incidence (co)algebras. In the present contribution, after establishing a formula for the section coefficients, we survey a large supply of examples, emphasising the notion’s firm roots in classical combinatorics. The first batch of examples, similar to binomial posets, serves to illustrate two key points: (1) the incidence algebra in question is realised directly from a decomposition space, without a reduction step, and reductions are often given by CULF\xspace functors; (2) at the objective level, the convolution algebra is a monoidal structure of species. Specifically, we encounter the usual Cauchy product of species, the shuffle product of L \mathbb L -species, the Dirichlet product of arithmetic species, the Joyal–Street external product of q q -species and the Morrison ‘Cauchy’ product of q q -species, and in each case a power series representation results from taking cardinality. The external product of q q -species exemplifies the fact that Waldhausen’s S ∙ S_\bullet -construction on an abelian category is a decomposition space, yielding Hall algebras. The next class of examples includes Schmitt’s chromatic Hopf algebra, the Faà di Bruno\xspace bialgebra, the Butcher–Connes–Kreimer Hopf algebra of trees, and several variations from operad theory. Similar structures on posets and directed graphs exemplify a general construction of decomposition spaces from directed restriction species. A short appetiser on decomposition spaces of symmetric functions is included, featuring the base change from elementary symmetric functions to monomial symmetric functions, modelled as a span of decomposition spaces. We finish by computing the Möbius\xspace function in a few cases, exhibiting a few techniques, and commenting on certain cancellations that occur in the process of taking cardinality, substantiating that these cancellations are not always possible at the objective level.