Separable and Equatable Hypergraphs

DOI10.1016/J.DAM.2023.03.019arXiv2206.07517MaRDI QIDQ6402177FDOQ6402177

Authors: Daniel Deza, Shmuel Onn 

Publication date: 6 June 2022

Abstract: We consider the class of {em separable} $k$-hypergraphs, which can be viewed as uniform analogs of threshold Boolean functions, and the class of {em equatable} $k$-hypergraphs. We show that every $k$-hypergraph is either separable or equatable but not both. We raise several questions asking which classes of equatable (and separable) hypergraphs enjoy certain appealing characterizing properties, which can be viewed as uniform analogs of the $2$-summable and $2$-monotone Boolean function properties. In particular, we introduce the property of {em exchangeability}, and show that all these questioned characterizations hold for graphs, multipartite $k$-hypergraphs for all $k$, paving $k$-matroids and binary $k$-matroids for all $k$, and $3$-matroids, which are all equatable if and only if they are exchangeable. We also discuss the complexity of deciding if a hypergraph is separable, and in particular, show that it requires exponential time for paving matroids presented by independence oracles, and can be done in polynomial time for binary matroids presented by such oracles.

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial aspects of matroids and geometric lattices (05B35) Hypergraphs (05C65)

This page was built for publication: Separable and Equatable Hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6402177)