An Entropy-Based Approach to the Union-Closed Sets Conjecture
Understanding the chaos of entropy in combinatorics
W.G. Antvelink (TU Delft - Electrical Engineering, Mathematics and Computer Science)
A. Bishnoi – Mentor (TU Delft - Electrical Engineering, Mathematics and Computer Science)
B.M. Terhal – Mentor (TU Delft - QCD/Terhal Group)
R. Versendaal – Graduation committee member (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Y.M. Blanter – Graduation committee member (TU Delft - Applied Sciences)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
The Union-Closed Sets Conjecture (UCSC), posed by Peter Frankl in 1979, asserts that every finite union-closed family of sets contains an element that appears in at least half of its member sets. Despite this seemingly simple formulation, the conjecture has remained unresolved for decades. Recently in November 2022 Gilmer developed a novel approach based on the information theoretic concept: \emph{entropy}, which has offered fresh insights and promising partial results. In this thesis, we provide a self-contained introduction to entropy and explore its utility in combinatorics, specifically its application to the UCSC. We thoroughly examine the groundbreaking entropy-based proof that establishes a constant lower bound of \(\frac{3 - \sqrt{5}}{2}\approx0.382\). Additionally, we shortly discuss the small further improvements made to this bound. We then consider a related conjecture proposed by Nagel, which states: \textit{the \(k\)th most frequent element in a union-closed family appears in at least a fraction \(\frac{1}{2^{k-1} +1}\) of the sets.} We shall discuss how the new entropy approach could also be used there to improve the bounds on the sizes of the family.
All these explorations have been focused on understanding recent developments and to create a unified narrative. Due to time constraints, the thesis did not pursue new results. However, the comprehensive understanding gained has given some promising directions for future research.