New conjectures for union-closed families

MaRDI QIDQ311524zbMATH OpenFDO

Authors Jonad Pulaj, Annie Raymond, Dirk Oliver Theis

Publication date 13 September 2016

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

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

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

integer programmingFrankl conjectureunion-closed families

Mathematics Subject Classification ID

Integer programming (90C10) Extremal set theory (05D05)

Abstract: The Frankl conjecture, also known as the union-closed sets conjecture, states that in any finite non-empty union-closed family, there exists an element in at least half of the sets. From an optimization point of view, one could instead prove that $2a$ is an upper bound to the number of sets in a union-closed family on a ground set of $n$ elements where each element is in at most $a$ sets for all $a,ninmathbb{N}^{+}$. Similarly, one could prove that the minimum number of sets containing the most frequent element in a (non-empty) union-closed family with $m$ sets and $n$ elements is at least $fracm2$ for any $m,ninmathbb{N}^{+}$. Formulating these problems as integer programs, we observe that the optimal values we computed do not vary with $n$. We formalize these observations as conjectures, and show that they are not equivalent to the Frankl conjecture while still having wide-reaching implications if proven true. Finally, we prove special cases of the new conjectures and discuss possible approaches to solve them completely.

Recommendations

• The union-closed sets conjecture for small families
• Well-graded families and the union-closed sets conjecture
• New bounds for union-free families of sets
• Publication:4204156
• On the union-closed sets conjecture
• A note on the union-closed sets conjecture
• scientific article; zbMATH DE number 2065940
• scientific article; zbMATH DE number 729129
• Union-closed families of sets
• Union-closed families of sets

Cites work

• scientific article; zbMATH DE number 32091 (Why is no real title available?)
• scientific article; zbMATH DE number 4123737 (Why is no real title available?)
• scientific article; zbMATH DE number 528796 (Why is no real title available?)
• scientific article; zbMATH DE number 718666 (Why is no real title available?)
• scientific article; zbMATH DE number 729129 (Why is no real title available?)
• scientific article; zbMATH DE number 2114680 (Why is no real title available?)
• scientific article; zbMATH DE number 844158 (Why is no real title available?)
• scientific article; zbMATH DE number 4195951 (Why is no real title available?)
• A graph-theoretic version of the union-closed sets conjecture
• A new perspective on the union-closed sets conjecture.
• A stability result for the union-closed size problem
• An Average Set Size Theorem
• FC-families and improved bounds for Frankl's conjecture
• Families implying the Frankl conjecture
• Formalizing Frankl's conjecture: FC-families
• Frankl's conjecture is true for lower semimodular lattices
• Frankl's conjecture is true for modular lattices
• Lower semimodular types of lattices: Frankl's conjecture holds for lower quasi-semimodular lattices
• Minimal weight in union-closed families
• Minimizing the weight of the union-closure of families of two-sets
• Note on the union-closed sets conjecture
• On averaging Frankl's conjecture for large union-closed-sets
• On conjectures of Frankl and El‐Zahar
• On the scope of averaging for Frankl's conjecture
• On the trace of finite sets
• On union-closed families. I
• On union-closed sets and Conway's sequence
• Strong semimodular lattices and Frankl's conjecture
• The 11-element case of Frankl's conjecture
• The journey of the union-closed sets conjecture
• The union-closed sets conjecture almost holds for almost all random bipartite graphs
• Union-closed families
• Union-closed families of sets

Cited in

(7)

• On verifying and engineering the wellgradedness of a union-closed family
• scientific article; zbMATH DE number 7595025 (Why is no real title available?)
• A proof of Frankl's conjecture on cross-union families
• Cutting planes for families implying Frankl's conjecture
• Well-graded families and the union-closed sets conjecture
• Progress on the union-closed conjecture and offsprings in Winter 2022--2023
• Characterizing 3-Sets in Union-Closed Families

This page was built for publication: New conjectures for union-closed families

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