Union-closed sets and Horn Boolean functions

Lozin, Vadim and Zamaraev, Viktor ORCID: 0000-0001-5755-4141 (2024) Union-closed sets and Horn Boolean functions. Journal of Combinatorial Theory, Series A, 202. p. 105818.

Access the full-text of this item by clicking on the Open Access link.

Official URL: http://dx.doi.org/10.1016/j.jcta.2023.105818

Abstract

A family F of sets is union-closed if the union of any two sets from F belongs to F. The union-closed sets conjecture states that if F is a finite union-closed family of finite sets, then there is an element that belongs to at least half of the sets in F. The conjecture has several equivalent formulations in terms of other combinatorial structures such as lattices and graphs. In its whole generality the conjecture remains wide open, but it was verified for various important classes of lattices, such as lower semimodular lattices, and graphs, such as chordal bipartite graphs. In the present paper we develop a Boolean approach to the conjecture and verify it for several classes of Boolean functions, such as submodular functions and double Horn functions.

Item Type:	Article
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	02 Nov 2023 09:41
Last Modified:	03 Feb 2024 17:49
DOI:	10.1016/j.jcta.2023.105818
Open Access URL:	https://doi.org/10.1016/j.jcta.2023.105818
Related URLs:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3176498