A Study On The Graph Formulation Of Union Closed Conjecture
Nived J M


A Digital signature scheme based on Module-LWE and Module-SIS
    Abbas Maarefparvar
    
=============================================================









§ ABSTRACT 
  The Union Closed Conjecture, posed by Peter Frankl in 1979, is one of the most renowned problems in Combinatorics. Its appeal stems from the simplicity of its statement and the potential complexity of its solution. The conjecture asserts that in any union-closed family of sets, there exists an element that belongs to at least half of the sets in the family.

This paper explores the graph-theoretic formulation of the conjecture and establishes connections between the set-based and graph-based formulations. Through this connection, we derive new results and provide proofs for specific classes of graphs. Additionally, by analyzing the distribution of pendant vertices within various graphs, we demonstrate the validity of the conjecture for a broader range of graph classes.


Keywords: Union Closed Conjecture, Frequency, Family of sets, Member sets, Pendant vertices.






§ INTRODUCTION


The Union Closed Conjecture, colloquially known as Frankl's Conjecture, was initially formulated by Peter Frankl in 1979. The conjecture pertains to a class of sets referred to as union closed families, wherein the union of any two member sets remains a member set itself. Specifically, the conjecture posits that for every finite union closed family of sets, excluding families comprising solely the empty set, there exists an element belonging to at least half of the member sets. In this context, a finite union closed family is defined as having both a finite number of member sets and finite cardinality for each member set.

A natural extension of this conjecture to infinite cases was considered, but Poonen <cit.> identified counterexamples such as families with member sets of the form {i,i+1,i+2,...} where i ∈ℕ. In this scenario, each element i has finite frequency, challenging the conjecture's applicability to families with an infinite number of member sets. Furthermore, a preference is expressed for member sets with finite cardinality.

The notion of separation within a family is introduced, wherein elements x and y are considered separated by the family 𝒜 if there exists a member set A ∈𝒜 such that either x or y is an element of A, but not both. A family 𝒜 is termed a separating family if any two distinct elements are separated by 𝒜. Notably, a pair of non-separated elements can be treated as a single element without affecting the conjecture's determining factors namely, the cardinality of 𝒜 and the possible frequencies of elements. Thus, the conjecture only needs verification for all finite separating families.

 
In Section <ref>, we present the necessary notations, definitions, and formulations to address the problem. We explore both the set formulation and graph formulation of the conjecture, and also discuss some previously known results in this area. Moving on to Section <ref>, we establish the connection between the two formulations and provide equivalent versions of existing results. Additionally, we demonstrate the validity of the conjecture for certain graph classes. Finally, in Section <ref>, we introduce an intriguing theorem that proves the conjecture for graphs with pendant vertices on specific locations, and discuss some of its consequences.
 








§ PRELIMINARIES






 We will introduce certain notations and endeavor to mathematically analyze the given problem. We say that a given family of sets 𝒜 is union closed if, for every pair of the member sets A,B ∈𝒜 we have A∪ B∈𝒜. The union of all the member sets of 𝒜 is called the universe of 𝒜, represented by U(𝒜). 


    U(𝒜)=⋃_A∈𝒜A={x∈ A :A∈𝒜}


The frequency of an element x∈U(𝒜) denoted by μ(x), is the number of member sets of 𝒜 containing x. Using the above notations, we can state the Frankl's conjecture as:

*conjecture*Union Closed Conjecture

If 𝒜 is a finite union closed family of sets with 𝒜≠{ϕ}, then there exists x ∈U(𝒜) such that μ(x) ≥1/2|𝒜|. We call x an abundant element.


Similar to a union closed family, we define an intersection-closed family as a collection of sets closed under intersection. Now, using intersection closed families, we can reformulate the Union Closed Conjecture.



*ConjectureIntersection Closed Conjecture


Any finite intersection closed family with at least two member sets has an element which is part of at most half of the member sets. That is, if ℬ is an intersection closed family of sets with |ℬ| ≥ 2, then there exists x ∈U(ℬ) satisfying μ(x) ≤1/2|ℬ|. We call x a rare element.








<cit.>
Union closed conjecture is equivalent to the Intersection closed conjecture.



Despite being open for over forty years, the conjecture remains largely elusive. Here, I will outline some of the known results concerning union closed families. We denote the cardinality of the universe by m and the number of member sets by n. The following are some scenarios where a separating family satisfies the Union Closed Conjecture:




    
  * When m ≤ 12. <cit.>
    

    
  * When n ≤ 50. <cit.>
    

    
  * When n ≤ 2m.<cit.>
    

    
  * When n ≥2/32^m.<cit.>
    

    
  * When the family includes either a singleton set or a set of cardinality.<cit.>
    

    
  * When all the member sets of the family are having a cardinality at least m/2.<cit.>
    




















 §.§ The graph formulation




Using some notions of graph theory, Henning Bruhn<cit.> proposed a graph formulation to the union closed conjecture in 2013. In this section, we will go through the crux of the interpretation. A vertex subset of a graph is said to be a stable set if any pair of its elements are non- adjacent. Introducing the concept of maximality in stable sets, we define a stable set as maximal if no additional vertex can be added to it without violating the condition of being a stable set. For a graph G, V(G) represents the set of vertices. We use the notation N(P) [We use N_ G(P) specifically if more than one graphs are present] to represent the set of neighbors of a vertex subset P⊆ V(G). When P is a singleton, denoted as P={x}, we use N(x) instead of N({x}).




<cit.>
For any bipartite graph with at least one edge, there exists a vertex in each of its bipartite classes that lie in at most half of the maximal stable sets.



<cit.>
Conjecture <ref> is equivalent to Frankl's conjecture.


The conjecture <ref> mentioned above represents the graph formulation of Frankl's conjecture. Considering its equivalence with Frankl's conjecture, a vertex v in graph G is deemed rare if it appears in at most half of the maximal stable sets. We define a bipartite graph to satisfy Frankl's conjecture if Conjecture <ref> holds for it.











Currently, bipartite graph classes such as chordal bipartite, subcubic, and series-parallel graphs are known to satisfy Frankl's Conjecture <cit.>.


§ CONNECTING THE TWO FORMULATIONS.


In the previous section, we extensively discussed both the graph formulation and the set formulation of the Union Closed Conjecture, along with significant results pertaining to each. Now, we aim to establish connections between these two formulations and present equivalent results derived from one to the other, and vice versa.

Let us consider a family of sets 𝒮 with the universe U(𝒮). The union closed family generated by 𝒮, denoted by ⟨𝒮⟩, comprises the collection of all unions of its member sets, including the empty set ϕ. We define the incidence graph of 𝒮 as a bipartite graph G with vertex set V(G) = 𝒮∪ U(𝒮) and edge set E(G) = {Sx : S ∈𝒮, x ∈ U(𝒮), x ∈ S }. Let G be a bipartite graph with bipartite classes X and Y. By the incidence family of X, we refer to the family ℱ^ X = {N(y) : y ∈ Y}. If there are no isolated vertices[As isolated vertices does not affect the conjecture, we can just exclude them.] in X, then it's universe U(ℱ^ X)=X. Throughout this section, we will denote the two vertex classes of the bipartite graph G as X and Y.




    Let G be a bipartite graph with vertex partition X∪ Y. A vertex x∈ X is rare if and only if it is abundant in ⟨ℱ^ X⟩.




  Consider any subset of vertices from Y, denoted as Y^'. It can be observed that there exists a unique maximal stable set in G, denoted as S, such that S∩ X=X∖ N(Y^'). Furthermore, every maximal stable set S satisfies S∩ X=X∖ N(Y^') for some Y^'⊆ Y. It is important to note that no two maximal stable sets S_ 1 and S_ 2 can have the same intersection with X, i.e., S_ 1∩ X ≠ S_ 2∩ X. Therefore, if a vertex x∈ X is rare in G, then it is also rare in the family {X∖ (N(Y^')) | Y^'⊆ Y}. Consequently, x is abundant in the family { (N(Y^')) | Y^'⊆ Y}. Now, let F={N(y)| y∈ Y^'}, and observe that the universe U(F) is nothing but N(Y^'). It is also evident that { (N(Y^')) | Y^'⊆ Y}={U(F)|F⊆ℱ^ X}=⟨ℱ^ X⟩. The converse direction follows similarly from the above steps.

      
In accordance with the definition of separating families presented in the preceding section, let us introduce the concept of a twin-free graph as a graph devoid of any pair of vertices sharing an identical set of neighbors. If there are two vertices in a graph that have the exact same neighbors, combining them into one vertex would not alter the count of maximal stable sets or the potential frequencies within the graph. Hence, our focus remains solely on verifying the conjecture for all twin-free bipartite graphs. It is pertinent to note that this section exclusively deals with twin-free graphs with no isolated vertices.


  If G is a bipartite graph with one of its two classes containing at most 12 vertices, then there exists a rare vertex within the same class.




    Let X denote the bipartite class of G such that |X| ≤ 12. Then, it is evident that |U(⟨ℱ^ X⟩)| = |U(ℱ^ X)| = |X| ≤ 12. It is known that union closed families with at most 12 elements satisfy the conjecture. Therefore, ⟨ℱ^ X⟩ satisfies the conjecture, and consequently, there exists a rare vertex in X by Proposition <ref>.





    A bipartite graph with both classes of cardinality at most 12 satisfies Frankl's conjecture.






     In a bipartite graph G=(X,Y), if 2^ |Y|≤ 2|X|, then there exists a rare vertex in X.




   Consider the union closed family ⟨ℱ^ X⟩. Clearly, the number of member sets in the family, n=|⟨ℱ^ X⟩|≤ 2^0.5|ℱ^0.5X|= 2^0.5|Y|. Also, note that the total number of elements m=U(ℱ^ X)=|X|. This leads us to the relation n≤ 2^|Y|≤ 2|X| = 2m. Since n≤ 2m, ⟨ℱ^ X⟩ satisfies the conjecture. Hence, there is a rare element in X.




     If |Y|≥2/32^ |X|, then the graph satisfies Frankl's conjecture.




The number of member sets in ⟨ℱ^ X⟩, denoted by n = |⟨ℱ^ X⟩| ≥ |ℱ^ X| = |Y|, and the number of elements in the universe of ⟨ℱ^ X⟩ is m = |X|. Thus, the relation |Y| ≥2/32^ |X| leads us to n ≥2/32^ m, and hence ⟨ℱ^ X⟩ satisfies the conjecture. This ensures a rare element in X. Now, observe that |Y| ≥2/32^ |X| 2|Y| ≥4/32^ |X|≥ 2^ |X|. By Proposition <ref>, there exists a rare element in Y, and as a result, the graph satisfies the conjecture.







    If a bipartite graph G contains a pendant vertex, then its neighbor is rare in G. Additionally, if G contains a vertex of degree 2, then there exists a rare vertex in the other bipartite class.




Let y ∈ Y be the pendant vertex. Then, ⟨ℱ^ X⟩ contains a singleton. Therefore, ⟨ℱ^ X⟩ satisfies the conjecture, and moreover, the neighbor of y is the abundant element of the family. Hence, the neighbor of y is a rare vertex of G. Similarly, when there is a vertex of degree 2 in Y, ⟨ℱ^ X⟩ contains a member set of cardinality 2, and as a result, ⟨ℱ^ X⟩ has an abundant element. Hence, there is a rare vertex in X.





  Let ℱ be a family in which every member set has a maximum size of 3, and each element within the sets has a frequency that does not exceed 3. Then ⟨ℱ⟩ satisfies the union closed conjecture.




    The proof is straightforward, as the incidence graph of ℱ is subcubic and we know that subcubic graphs satisfy the union closed conjecture.



 

   If ℱ is a family with n member sets, and it contains an element with a frequency of at least n - ⌊log_2n/2⌋, then ⟨ℱ⟩ satisfies the union closed conjecture, and that element is abundant.




     Let's consider an element a in ℱ with a frequency of at least n - ⌊log_2n/2⌋. Among the sets in ℱ, there are at most ⌊log_2n/2⌋ that don't contain a. We can observe that the maximum number of sets, including the empty set, in ⟨ℱ⟩ that don't include a is determined by the power set of ⌊log_2n/2⌋ elements. Essentially, we can consider any combination of these sets. Consequently, there are at most 2^⌊log_2n/2⌋ = ⌊n/2⌋ sets in ⟨ℱ⟩ that exclude a. Since ⌊n/2⌋≤|⟨ℱ⟩|/2, this observation leads to the conclusion that a is present in at least half of the sets in ⟨ℱ⟩.





    Let G be a bipartite graph with bipartite classes X and Y. If there exists a vertex a ∈ X such that |N(a)| ≥ |Y| - ⌊log_2|Y|/2⌋, then a is a rare vertex.




    The proof follows straightforwardly from Proposition <ref> in conjunction with Proposition <ref>.






 Let G be a bipartite graph with bipartite classes X and Y. If deg(a)≥|X|/2 for every vertex a∈ Y, then there is a rare vertex in X.



    It can be observed that the cardinality of the member sets of ℱ^ X is greater than |X|/2. Consequently, the cardinality of the member sets of ⟨ℱ^ X⟩ is also greater than |X|/2. Thus, ⟨ℱ^ X⟩ satisfies the conjecture, and as a result, there is a rare vertex in X. 



    Let G be a bipartite graph with a minimum degree of δ. If both bipartite classes have cardinalities at most 2δ, then G satisfies Frankl's conjecture.

   












    An r-regular bipartite graph with both of its bipartite classes having cardinality at most 2r satisfies Frankl's conjecture.







    Any bipartite graph with no pendant vertex satisfy Frankl's conjecture.



    Any bipartite graph with exactly one pendant vertex satisfy Frankl's conjecture.



    Any bipartite graph with at least one pendant vertex satisfy Frankl's conjecture.



    Conjectures <ref>, <ref>, and <ref> are equivalent to each other. Additionally, a proof of any one of these conjectures would imply the validity of the union closed conjecture.


Let's consider a union closed family ℱ. It's known that if ℱ contains a singleton set, it trivially satisfies the union closed conjecture. Now, let's assume ℱ to be a union closed family without singletons.

The incidence graph of ℱ either lacks pendant vertices entirely, or if they exist, they are all adjacent to the same vertex. This is because in the union closed family ℱ, U(ℱ) is a member set, and any element with frequency 1 must belong to that set. Also, note that the conjecture's truth value remains unchanged by adding or removing an element of frequency 1 from the family's universe.

Assuming Conjecture <ref> to be true, if ℱ contains elements of frequency 1, we can remove them to obtain a new family ℱ'. The incidence graph of ℱ' has no pendant vertices. By applying Proposition <ref>, we conclude that ℱ' satisfies the union closed conjecture, and so does the original family ℱ. Similarly, the equivalence of Conjectures <ref> and <ref> can be demonstrated by adding elements of frequency 1 to the respective families.



The Proposition mentioned above, Proposition <ref>, helps to narrow down the specific classes of graphs that need to be considered in order to demonstrate the conjecture. In the subsequent section, our focus will be on graphs that possess pendant vertices positioned in specific locations.










§ SOME NEW GRAPH RESULTS


We will see some interesting results related to the graph formulation of the conjecture. Before that let us go through some definitions and notations we might encounter here.

For a graph G, we denote the set of all maximal stable sets by ℬ_ G. The cardinality of ℬ_ G is denoted by w_ G, which represents the number of maximal stable sets of G. For any vertex x ∈ V(G), the number of maximal stable sets containing x is represented by w_ G(x). We use the notation N_ G(P) to represent the set of neighbors of a vertex subset P in graph G. When P is a singleton, say P = {x}, we will simply use N_ G(x).



If a disconnected graph G has one of its connected components satisfying Frankl's conjecture, then G will also satisfy the conjecture.





    As Frankl's conjecture is about finite graphs, we only need to consider finitely many connected components. We will show this for the case of two components, and the rest of the proof follows from basic induction arguments. Suppose G has two components P and Q. Let S_ 1 and S_ 2 be two maximal stable sets of P and Q respectively. One can notice that S_ 1∪ S_ 2 is a maximal stable set of G. For any maximal stable set S of G, observe that S ∩ V(P) and S ∩ V(Q) are maximal stable sets of P and Q respectively. This gives the number of maximal stable sets of G, w_ G = w_ P w_ Q. Using similar arguments, one can obtain that for every x ∈ V(P), w_ G(x) = w_ P(x) w_ Q.

Let r be a rare vertex in P. Then by definition, w_ P - 2w_ P(r) ≥ 0. As a result, w_ G - 2w_ G(r) = w_ P w_ Q - 2w_ P(r) w_ Q≥ 0 and r is rare in G. Thus, whenever P satisfies the conjecture, it guarantees that it holds for G as well.
 









    


We will now present a more intriguing result. A decomposition of a graph G is a set of edge-disjoint subgraphs H_1, H_2, …, H_n such that ⋃_ i=1^ n H_i = G. A vertex v ∈ V(G) is defined as 2-layered if every vertex in N_ G(v) has a pendant vertex adjacent to it.





    Let G be a bipartite graph and {C,H} a decomposition of G. Suppose the vertices in V(C) ∩ V(H) belong to the same bipartite class of G and are all 2-layered. Then, all rare vertices in C or H will remain rare in G.



Before presenting the proof of the theorem, we need to establish some notations and lemmas. The following notations will be used throughout the proof. In light of <ref>, it suffices to verify the theorem for connected graphs. Consequently, we assume without loss of generality that G is connected.



Let m ∈ V(C) ∩ V(H), and suppose N_ C(m) = ϕ. In this case, we can simply remove the vertex from C to get a new decomposition. Similarly, if N_ H(m) = ∅, we can remove m from H. This allows us to redefine C and H in such a way that every vertex in V(C) ∩ V(H) has neighbors in both C and H. Let 1, 2, …, n be the vertices common to these subgraphs C and H. We define [n] = {i ∈ℕ| i ≤ n}, and accordingly, we represent this common vertex set by [n]. For any subset Θ⊆ [n], we denote its complement by Θ^𝖼 = [n] ∖Θ.




Recall the definitions of w_ G and ℬ_ G. Here, we will slightly generalize these definitions.For any vertex subsets P, Q ⊆ V(G) and any subgraph H of G, the notation ℬ_ G(P, Q) denotes the set of all maximal stable sets of G that include all vertices in P and exclude all vertices in Q. Similarly, ℬ_ H(P, Q) represents the set of all maximal stable sets of H with the same inclusion and exclusion criteria. The cardinality of ℬ_ G(P, Q) and ℬ_ H(P, Q) is denoted by w_ G(P, Q) and w_ H(P, Q). This notation is somewhat informal but helps to reduce the complexity of larger notations.




   For any Θ⊆ [n], Γ⊆Θ^𝖼, and b ∈ V(C∖Γ), the following identities hold:

    w_ C∖Γ(Θ, Θ^𝖼∪ N_ C(Γ)) = w_ C(Θ∪Γ, Θ^𝖼∖Γ)


    w_ C∖Γ({b}∪Θ, Θ^𝖼∪ N_ C(Γ)) = w_ C({b}∪Θ∪Γ, Θ^𝖼∖Γ)






Consider the mapping f: ℬ_ C∖Γ(Θ, Θ^𝖼∪ N_ C(Γ)) →ℬ_ C(Θ∪Γ, Θ^𝖼∖Γ) defined by f(B) = B ∪Γ. Let B ∈ℬ C∖Γ(Θ, Θ^𝖼∪ N C(Γ)), observe that f(B) includes all vertices from Θ∪Γ and excludes all vertices from Θ^𝖼∖Γ. Since B is a stable set in C ∖Γ and contains no vertices from N_ C(Γ), it follows that f(B) is stable in C. Assume, for contradiction, that f(B) is not a maximal stable set in C. Then, there exists a vertex v ∈ V(C) such that v ∉ f(B) and B ∪Γ∪{v} is stable in C. This implies that B ∪{v} is stable in C ∖Γ, contradicting the maximality of B in C ∖Γ. Hence, f(B) ∈ℬ_ C(Θ∪Γ, Θ^𝖼∖Γ). 



Next, consider a set D ∈ℬ_ C(Θ∪Γ, Θ^𝖼∖Γ). We define the inverse image of D under the mapping f as f^-1(D) = D ∖Γ. Since D necessarily includes all vertices from Γ, it excludes any vertices from N_ C(Γ). Therefore, f^-1(D) is clearly a subset of V(C ∖Γ) that contains all vertices in Θ, while simultaneously avoiding all vertices in Θ^𝖼∖Γ and N_ C(Γ).






Also note that D is a stable set, and since f^-1(D) is a subset of D, it is also a stable set. Suppose, for contradiction, that f^-1(D) is not maximal stable in C ∖Γ. This implies there exists a vertex v ∈ V(C ∖Γ), with v ∉ f^-1(D), such that the set {v}∪ f^-1(D) is stable in C ∖Γ. Since all vertices in Γ are 2-layered, each vertex in N_ C(Γ) has an adjacent pendant vertex. Due to the maximality of the stable sets, these pendant vertices must be included in all member sets of ℬ_ C(Θ∪Γ, Θ^𝖼∖Γ). Consequently, they are present in every member set of f^-1(ℬ_ C(Θ∪Γ, Θ^𝖼∖Γ)). Thus, v ∉ N_ C(Γ). Therefore, {v}∪ D = {v}∪ f^-1(D) ∪Γ would be stable in C, which contradicts the assumption that D is a maximal stable set in C. Hence, f^-1(D) ∈ℬ_ C ∖Γ(Θ, Θ^𝖼∪ N_ C(Γ)) and the mapping is well-defined.





I
It is trivial that f is a bijective map. The one-to-one correspondence between the families ℬ_ C ∖Γ(Θ, Θ^𝖼∪ N_ C(Γ)) and ℬ_ C(Θ∪Γ, Θ^𝖼∖Γ) establishes Equation <ref>. Similarly, Equation <ref> follows from analogous arguments, as it involves collecting all maximal stable sets containing the specified vertex b ∈ V(C ∖Γ) from both families.
















     For any Θ⊆[n], Γ_ 1,Γ_ 2⊆Θ^𝖼 and b∈ V(C), if Γ_ 1≠Γ_ 2 then,
    
    ℬ_ C∖Γ_ 1(Θ,Θ^𝖼∪ N_ C( Γ_ 1))  
         ∩ℬ_ C∖Γ_ 2(Θ,Θ^𝖼∪ N_ C( Γ_ 2))=ϕ

    
    
    ℬ_ C∖Γ_ 1({b}∪Θ,Θ^𝖼∪ N_ C( Γ_ 1))  
         ∩ℬ_ C∖Γ_ 2({b}∪Θ,Θ^𝖼∪ N_ C( Γ_ 2))=ϕ














Consider two distinct subsets Γ_ 1 and Γ_ 2 of Θ^𝖼. Without loss of generality, assume that there exists an element m ∈Γ_ 1 such that m ∉Γ_ 2. Suppose B is an element of both ℬ_ C ∖Γ_ 1(Θ, Θ^𝖼∪ N_ C(Γ_ 1)) and ℬ_ C ∖Γ_ 2(Θ, Θ^𝖼∪ N_ C(Γ_ 2)). Since m ∈Γ_ 1, the maximal stable sets in ℬ_ C ∖Γ_ 1(Θ, Θ^𝖼∪ N_ C(Γ_ 1)) avoid all vertices in N_ C(m). Therefore, B ∩ N_ C(m) = ∅. On the other hand, since B is also an element of ℬ_ C ∖Γ_ 2(Θ, Θ^𝖼∪ N_ C(Γ_ 2)), it must be a maximal stable set in C ∖Γ_ 2 that excludes vertices from Θ^𝖼. Given that m ∈Θ^𝖼, the maximality of B implies that B ∩ N_ C(m) ≠∅. 

This contradiction shows that ℬ_ C ∖Γ_ 1(Θ, Θ^𝖼∪ N_ C(Γ_ 1)) ∩ℬ_ C ∖Γ_ 2(Θ, Θ^𝖼∪ N_ C(Γ_ 2)) must be empty. Furthermore, it follows that ℬ_ C ∖Γ({b}∪Θ, Θ^𝖼∪ N_ C(Γ)) ⊆ℬ_ C ∖Γ(Θ, Θ^𝖼∪ N_ C(Γ)). Consequently, we deduce that ℬ_ C ∖Γ_ 1({b}∪Θ, Θ^𝖼∪ N_ C(Γ_ 1)) ∩ℬ_ C ∖Γ_ 2({b}∪Θ, Θ^𝖼∪ N_ C(Γ_ 2)) = ∅.









 Let b∈ V(C∖ [n]) and a∈ [n], then :
 
    w_ G=∑_Θ⊆[n]∑_Γ⊆Θ^𝖼{ w_ C∖Γ(Θ,Θ^𝖼∪ N_ C(Γ))
    ∑_Ψ⊆Θ^𝖼∖Γ
     w_ H∖Ψ(Θ,Θ^𝖼∪ N_ H(Ψ))}


    w_ G(b)=∑_Θ⊆[n]∑_Γ⊆Θ^𝖼{ w_ C∖Γ({b}∪Θ,Θ^𝖼∪ N_ C(Γ))
    ∑_Ψ⊆Θ^𝖼∖Γ
     w_ H∖Ψ(Θ,Θ^𝖼∪ N_ H(Ψ))}


    w_ G(a)=∑_Θ⊆[n]∑_Γ⊆Θ^𝖼{ w_ C∖Γ({a}∪Θ,Θ^𝖼∪ N_ C(Γ))
    ∑_Ψ⊆Θ^𝖼∖Γ
     w_ H∖Ψ({a}∪Θ,Θ^𝖼∪ N_ H(Ψ))}

   









    We will prove the equation <ref> by showing that,
    
    ℬ_ G ={B_1∪ B_2 |[ B_1∈ℬ_ C∖Γ(Θ,Θ^𝖼∪ N_ C(Γ)),  B_2∈ℬ_ H∖Ψ(Θ,Θ^𝖼∪ N_ C(Ψ));                                    Θ⊆ [n],Γ⊆Θ^𝖼,Ψ⊆Θ^𝖼∖Γ ]}.

    






For simplicity, let us denote the family on the right-hand side by 𝒟. Consider any member set B_1∪ B_2 in 𝒟. It is straightforward to observe that B_1∪ B_2 forms a stable set in G. If this set is not maximal in G, then there must exist a vertex v ∈ V(G) such that {v}∪ B_1∪ B_2 is also a stable set. However, due to the maximality of B_1 and B_2 in the subgraphs C ∖Γ and H ∖Ψ, respectively, the vertex v cannot belong to either of these subgraphs. Since C ∖Γ∪ H ∖Ψ = G, there is no such vertex v in the graph G. Therefore, B_1∪ B_2 must be a maximal stable set in G, implying that B_1∪ B_2∈ℬ_ G and hence 𝒟⊆ℬ_ G.






Now, consider any B ∈ℬ_ G. Define the subsets Θ⊆ [n] and Θ^𝖼 = [n] ∖Θ by setting Θ = B ∩ [n]. Next, define Γ, Ψ⊆Θ^𝖼 as the sets of vertices in [n] such that N_ C(Γ) ∩ B = ∅ and N_ H(Ψ) ∩ B = ∅, respectively. It is evident that Γ∩Ψ = ∅, because if there were a vertex v ∈Θ^𝖼 with N_ G(v) = N_ C(v) ∪ N_ H(v) = ∅, this would contradict the maximality of B as a stable set[Since v and none of its neighbors would be included in B]. Furthermore, B ∩ (C ∖Γ) contains all vertices in Θ but excludes vertices from both Θ^𝖼 and N_ C(Γ). Notably, this set is stable since it is a subset of B.





Assume that B is not maximal in C ∖Γ, and there exists a vertex v ∈ V(C ∖Γ) such that v ∉ B and ({v}∪ B) ∩ (C ∖Γ) is a stable set. For each u ∈Θ^𝖼∖Γ, by definition, N_ C(u) ∩ B ≠∅, which implies that v cannot belong to Θ^𝖼∖Γ. Consequently, v ∉ [n]. Note that v also does not belong to N_ C(Θ), as ({v}∪ B) ∩ (C ∖Γ) remains stable. From this, one can observe that ({v}∪ B) ∩ (H ∖Ψ) is also stable, and consequently, B ∪{v} = (({v}∪ B) ∩ (C ∖Γ)) ∪ (({v}∪ B) ∩ (H ∖Ψ)) forms a stable set in G, which contradicts the maximality of B. Therefore, B ∩ (C ∖Γ) ∈ℬ_ C∖Γ(Θ, Θ^𝖼∪ N_ C(Γ)). Similarly, one can show that B ∩ (H ∖Ψ) ∈ℬ_ H∖Ψ(Θ, Θ^𝖼∪ N_ C(Ψ)), and hence B ∈𝒟. This implies that ℬ_ G⊆𝒟.





 
Given that ℬ_ G = 𝒟, and with the application of Lemma <ref>, we derive Equation <ref>. The proof of Equation <ref> follows by identifying the member sets of both families that include b as an element. Similarly, Equation <ref> can be established using analogous reasoning.







We will determine the number of maximal stable sets using Lemma <ref>. First, let's apply Lemma <ref> to Equation <ref>.

    w_ G    = ∑_Θ⊆[n]∑_Γ⊆Θ^𝖼{ w_ C∖Γ(Θ,Θ^𝖼∪ N_ C(Γ))
    ∑_Ψ⊆Θ^𝖼∖Γ
    w_ H∖Ψ(Θ,Θ^𝖼∪ N_ H(Ψ))}
        =  ∑_Θ⊆[n]∑_Γ⊆Θ^𝖼{ w_ C(Θ∪Γ,Θ^𝖼∖Γ)
    ∑_Ψ⊆Θ^𝖼∖Γ
    w_ H(Θ∪Ψ,Θ^𝖼∖Ψ)}
 `
Notice that,

    ∑_Ψ⊆Θ^𝖼∖Γ
    w_ H(Θ∪Ψ,Θ^𝖼∖Ψ)     = ∑_Ψ⊆Θ^𝖼∖Γ
    w_ H(Θ∪Ψ,Γ∪ ((Θ^𝖼∖Γ)∖Ψ))   
        = w_ H(Θ,Γ)

 Observe that this identity holds because we are summing over all possible subsets Ψ⊆Θ^𝖼∖Γ. Next, we introduce a new variable Ω = Θ∪Γ, with Ω^𝖼 = [n] ∖Ω = Θ^𝖼∖Γ. This allows us to express w_ C(Θ∪Γ, Θ^𝖼∖Γ) as w_ C(Ω, Ω^𝖼). We can now apply this change of variables after substituting (<ref>) into equation (<ref>).

    w_ G    = ∑_Θ⊆[n]∑_Γ⊆Θ^𝖼{ w_ C(Θ∪Γ,Θ^𝖼∖Γ)
    w_ H(Θ,Γ)}[Substituting equation <ref>]
        =  ∑_Ω⊆[n]∑_Θ⊆Ω{ w_ C(Ω,Ω^𝖼)
    w_ H(Θ,Ω∖Θ)}[Change of variables]
        =  ∑_Ω⊆[n]{ w_ C(Ω,Ω^𝖼)  ∑_Θ⊆Ω
    w_ H(Θ,Ω∖Θ)}
        =  ∑_Ω⊆[n]{ w_ C(Ω,Ω^𝖼) w_ H}
        =  w_ C w_ H


In a similar manner, it can be deduced that w_ G(b) = w_ C(b)w_ H for any b ∈ C ∖ [n]. When a ∈ [n], for every Γ with a ∈Γ, we have w_ C ∖Γ({a}∪Θ, Θ^𝖼∪ N_ C(Γ)) = 0. Using this fact and after similar calculations, one can find that w_ G(a) ≤ w_ C(a)w_ H(a). Let r ∈ C be a rare vertex in C. If r ∈ C ∖ [n], we have w_ G-2w_ G(r)=w_ Cw_ H-2w_ C(r)w_ H=(w_ C-2w_ C(r))w_ H≥ 0. Now, if r ∈ [n], then w_ G-2w_ G(r)≥ w_ Cw_ H-2w_ C(r)w_ H(r)≥(w_ C-2w_ C(r))w_ H≥ 0. Therefore, every rare vertex in C is also rare in G.






























 






























The theorem's implications extend to solving the conjecture for previously unexplored graph classes, opening up new avenues of research. Now, let's discuss some of the notable consequences stemming from this result. All results concerning the set version of the union closed conjecture presented below are directly derived from the corresponding graph results by applying Proposition <ref> within the respective graph results.




     Let ℱ_ 1 and ℱ_ 2 be two families of sets that do not share any common sets. Let A denote the set of elements that are common to both families, i.e., A = U(ℱ_ 1) ∩ U(ℱ_ 2). Assume that every S ∈ℱ_ 1∪ℱ_ 2 with S ∩ A ≠∅ contains an element of frequency 1. If ⟨ℱ_ 1⟩ or ⟨ℱ_ 2⟩ satisfies the union closed conjecture, then ⟨ℱ_ 1∪ℱ_ 2⟩ also satisfies the conjecture.






   Let G be a bipartite graph and v ∈ V(G) be such that there exists at least one pendent vertex adjacent to v and all the non-pendent neighbors of v are 2-layered. Then G satisfies Frankl's conjecture. Furthermore, the vertex v and all of its neighbors are rare in G.


     Define P = {u | u ∈ N_ G(v), d(u) = 1}, where d(u) denotes the degree of vertex u. Let C be the subgraph induced by vertex v, while H is the subgraph induced by the vertex subset V(G) ∖ (P ∪{v}). Clearly, V(H) ∩ V(C) = N_ G(v) ∖ P, which corresponds to the non-pendant neighbors of v. 

     Observe that all vertices in N(v) ∖ P are 2-layered vertices, and {C, H} forms a decomposition of G. It is important to note that C is a star graph, implying that all of its vertices are rare within C. Consequently, by applying Theorem <ref>, we can conclude that both vertex v and its neighbors in G are rare in G, thereby establishing that G satisfies the conjecture.





   Let ℱ be a family of sets. Consider a member set A ∈ℱ that contains at least one element with frequency one. Suppose that for every set S ∈ℱ, where S ∩ A ≠∅, there exists an element within S that has frequency one. Under these conditions, the family ⟨ℱ⟩ satisfies the union closed conjecture, with all elements of A being abundant.

   


     Let G be a bipartite graph with no isolated vertices, in which every vertex in one of its bipartite classes is adjacent to at least one pendant vertex. Then, G satisfies Frankl's conjecture. In fact, all the vertices of G are rare.




     Let ℱ be a family of sets where each of it's member sets containing an element of frequency 1. Then ⟨ℱ⟩ satisfies the union closed conjecture. 
   




   Suppose we have a collection of bipartite graphs G_ 1, G_ 2, …, G_ k, where no two graphs share any common vertices. Additionally, let v_ 1, v_ 2, …, v_ k denote the 2-layered vertices within G_ 1, G_ 2, …, G_ k, respectively. By merging these k vertices, we obtain a new graph G. Under this construction, any vertex that is rare in one of the original graphs will remain rare in the composite graph G.



   Let v be the vertex in G resulting from the merging of all k vertices. It is evident that v is a 2-layered vertex, allowing us to apply Theorem <ref>.





   Let ℱ_ 1, ℱ_ 2, …, ℱ_ k be a collection of families of sets such that their universes are mutually exclusive. From each family ℱ_ i, choose an element a_ i such that every member set containing a_ i includes an element with frequency 1. Now, set a = a_ 1 = a_ 2 = … = a_ k and define ℱ = ⋃_i=1^kℱ_ i. Under this construction, all abundant elements in any of the ⟨ℱ_ i⟩ remain abundant in ⟨ℱ⟩.







§ ACKNOWLEDGMENTS


I would like to thank my adviser Rogers Mathew for guiding me through the right track.

























abbrv


