Monotone cohomologies and oriented matchings

In this paper, we extend the definition of cohomology associated to monotone graph properties, to encompass twisted functor coefficients.We introduce oriented matchings on graphs, and focus on their (twisted) cohomology groups. We characterise oriented matchings in terms of induced free-flow pseudoforests, and explicitly determine the homotopy type of the associated simplicial complexes. Furthermore, we provide a connection between the cohomology of oriented matchings with certain functor coefficients, and the recently defined multipath cohomology. Finally, we define a further oriented homology for graphs and interpret it as a count of free-flow orientations.

Keywords

poset homology, digraph, monotone property, matching complex, multipath complex

2010 Mathematics Subject Classification

05C70

Full Text (PDF format)

The first author acknowledges support from the École Polytechnique Fédérale de Lausanne via a collaboration agreement with the University of Aberdeen.

The second author was partially supported by the European Research Council (ERC) under the EU Horizon 2020 research and innovation programme (grant agreement No 674978), and by Hodgson–Rubinstein’s ARC grant DP190102363 “Classical And Quantum Invariants Of Low-Dimensional Manifolds”.

The third author was supported by the MIUR-PRIN project 2017JZ2SW5.

Received 17 August 2022

Received revised 28 August 2023

Accepted 6 November 2023

Published 2 October 2024