Matroid Horn functions

DOI10.1016/J.JCTA.2023.105838MaRDI QIDQ6187338zbMATH OpenFDO

Authors Kristóf Bérczi, Endre Boros, Kazuhisa Makino

Publication date 15 January 2024

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/2301.06642

zbMATH Keywords

Boolean minimizationHorn functionsmatroidsTurán systems

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Hypergraphs (05C65) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Hypergraph Horn functions were introduced as a subclass of Horn functions that can be represented by a collection of circular implication rules. These functions possess distinguished structural and computational properties. In particular, their characterizations in terms of implicate-duality and the closure operator provide extensions of matroid duality and the Mac Lane-Steinitz exchange property of matroid closure, respectively. In the present paper, we introduce a subclass of hypergraph Horn functions that we call matroid Horn functions. We provide multiple characterizations of matroid Horn functions in terms of their canonical and complete CNF representations. We also study the Boolean minimization problem for this class, where the goal is to find a minimum size representation of a matroid Horn function given by a CNF representation. While there are various ways to measure the size of a CNF, we focus on the number of circuits and circuit clauses. We determine the size of an optimal representation for binary matroids, and give lower and upper bounds in the uniform case. For uniform matroids, we show a strong connection between our problem and Tur'an systems that might be of independent combinatorial interest.

Recommendations

• Hypergraph Horn functions
• Directed hypergraphs and Horn minimization
• On a class of Boolean functions with matroid property
• Horn functions and their DNFs
• Horn functions and submodular Boolean functions

Cites work

• Approximating minimum representations of key Horn functions
• Computing intersections of Horn theories for reasoning with models
• Counting designs
• Covering triples by quadruples: an asymptotic solution
• Disjunctions of Horn theories and their cores
• Horn approximations of empirical data
• scientific article; zbMATH DE number 5852793 (Why is no real title available?)
• scientific article; zbMATH DE number 3534506 (Why is no real title available?)
• scientific article; zbMATH DE number 861622 (Why is no real title available?)
• scientific article; zbMATH DE number 5873618 (Why is no real title available?)
• Minimal coverings of pairs by triples
• On coverings
• Reasoning with models
• The complexity of theorem-proving procedures
• The decision problem for some classes of sentences without quantifiers
• The minimum equivalent DNF problem and shortest implicants
• What we know and what we do not know about Turán numbers

Cited in

(3)

• Hypergraph Horn functions
• On CNF formulas irredundant with respect to unit clause propagation
• Computing the D-base and D-relation in finite closure systems

This page was built for publication: Matroid Horn functions

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