A Formulation of the Union-Closed Sets Conjecture Using the Hamming Metric
Board Location: #177
Discipline: Mathematics and Statistics
Session: 1
Willoughby Caine - Fort Valley State University
Co-Author(s): Ishwari Kunwar, Fort Valley State University, Fort Valley, GA
A family of sets is union-closed if the union of any two sets in the family is also contained in the family. The Union-Closed Sets Conjecture, also known as Frankl’s Conjecture, posits that for any finite union-closed family of sets containing at least one nonempty set, there exists an element which belongs to at least half of the sets in the family. Although deceptively simple in its statement, the conjecture has defied a definitive proof, despite extensive study through various approaches and equivalent formulations, which have thus far yielded only partial results (Bruhn and Schaudt, 2015).
We introduce a new formulation of the conjecture based on the Hamming distance (metric) between sets, which is defined as the cardinality of their symmetric difference. Using this framework, we derive multiple equivalent formulations of the conjecture and provide a complete characterization of the set of all elements that satisfy the conjecture. Furthermore, we demonstrate that our approach enhances the averaging method, a widely used approach that has led to numerous partial results. We also obtain a criterion that relaxes the requirement of the averaging method for verifying the validity of the conjecture.
Our findings suggest that the Hamming metric provides a powerful perspective on the Union-Closed Sets Conjecture. By connecting structural properties of union-closed families to Hamming distances, this approach offers promising avenues for further exploration. Future research will focus on extending this framework to improve existing partial results and analyze larger families of sets, identifying additional equivalences, and hopefully progressing toward a complete proof of the conjecture.
References: Bruhn, H., & Schaudt, O. (2015). The journey of the Union-Closed sets conjecture. Graphs and Combinatorics, 31(6), 2043–2074. https://doi.org/10.1007/s00373-014-1515-0
Funder Acknowledgement(s): Funded by NSF grant awarded to TRiO College Access Programs at Fort Valley State University.
Faculty Advisor: Dr. Ishwari Kunwar, kunwari@fvsu.edu
Role: First, I read and annotated various papers to review extremal set theory and the Conjecture, coming up with a few approaches/representations to break down the Conjecture. After exploring on my own, I worked with my advisor to synthesize my work, and decide on the most relevant for use with the Hamming metric, which he suspected could be the basis for a good formulation for the Conjecture. He laid out ideas that would be useful/important to establishing the formulation, delineating the more difficult-to-prove theorems, and I wrote proofs for each as well as theorems I came up with on my own.