WA
W.G. Antvelink
info
Please Note
<p>This page displays the records of the person named above and is not linked to a unique person identifier. This record may need to be merged to a profile.</p>
1 records found
1
An Entropy-Based Approach to the Union-Closed Sets Conjecture
Understanding the chaos of entropy in combinatorics
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. ...
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. ...
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.
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.