Decision trees, monotone functions, and semimatroids
From MaRDI portal
Publication:6235979
arXiv1209.6365MaRDI QIDQ6235979FDOQ6235979
Authors: Jacob A. White 
Publication date: 27 September 2012
Abstract: We define decision trees for monotone functions on a simplicial complex. We define homology decidability of monotone functions, and show that various monotone functions related to semimatroids are homology decidable. Homology decidability is a generalization of semi-nonevasiveness, a notion due to Jonsson. The motivating example is the complex of bipartite graphs, whose Betti numbers are unknown in general. We show that these monotone functions have optimum decision trees, from which we can compute relative Betti numbers of related pairs of simplicial complexes. Moreover, these relative Betti numbers are coefficients of evaluations of the Tutte polynomial, and every semimatroid collapses onto its broken circuit complex.
This page was built for publication: Decision trees, monotone functions, and semimatroids
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6235979)
