Benjamin R. Jones - Minor-closed classes of binary functions

dmtcs:12230 - Discrete Mathematics & Theoretical Computer Science, November 4, 2024, vol. 26:3 - https://doi.org/10.46298/dmtcs.12230
Minor-closed classes of binary functionsArticle

Authors: Benjamin R. Jones

    Binary functions are a generalisation of the cocircuit spaces of binary matroids to arbitrary functions. Every rank function is assigned a binary function, and the deletion and contraction operations of binary functions generalise matroid deletion and contraction. We give the excluded minor characterisations for the classes of binary functions with well defined minors, and those with an associated rank function. Within these classes, we also characterise the classes of binary functions corresponding to polymatroids, matroids and binary matroids by their excluded minors. This gives a new proof of Tutte's excluded minor characterisation of binary matroids in the more generalised space of binary functions.


    Volume: vol. 26:3
    Section: Combinatorics
    Published on: November 4, 2024
    Accepted on: September 10, 2024
    Submitted on: September 5, 2023
    Keywords: Mathematics - Combinatorics,05B35 (Primary) 15A03, 05C83(Secondary)

    Consultation statistics

    This page has been seen 54 times.
    This article's PDF has been downloaded 20 times.