New conjectures for union-closed families

zbMATH Open1412.05193arXiv1512.00083MaRDI QIDQ311524FDOQ311524

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)

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.

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

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

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

zbMATH Keywords

integer programmingFrankl conjectureunion-closed families

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (6)

• Cutting planes for families implying Frankl's conjecture
• A proof of Frankl's conjecture on cross-union families
• On verifying and engineering the wellgradedness of a union-closed family
• Title not available (Why is that?)
• Well-graded families and the union-closed sets conjecture
• 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)