# The graph formulation of the union-closed sets conjecture

@article{Bruhn2015TheGF, title={The graph formulation of the union-closed sets conjecture}, author={Henning Bruhn and Pierre Charbit and Oliver Schaudt and Jan Arne Telle}, journal={Eur. J. Comb.}, year={2015}, volume={43}, pages={210-219} }

The union-closed sets conjecture asserts that in a finite non-trivial union-closed family of sets there has to be an element that belongs to at least half the sets. We show that this is equivalent to the conjecture that in a finite non-trivial graph there are two adjacent vertices each belonging to at most half of the maximal stable sets. In this graph formulation other special cases become natural. The conjecture is trivially true for non-bipartite graphs and we show that it holds also for the… Expand

#### 16 Citations

The union-closed sets conjecture almost holds for almost all random bipartite graphs

- Computer Science, Mathematics
- Eur. J. Comb.
- 2017

It is proved that, for every fixed edge-probability, almost every random bipartite graph almost satisfies Frankls conjecture. Expand

Union Closed Tree Convex Sets

- Mathematics, Computer Science
- FAW
- 2015

It is shown that the union closed sets conjecture holds for tree convex sets, and the proof relies on the well known Helly property of hypertrees and an equivalent graph formulation of the unionclosed sets conjecture. Expand

UNION CLOSED SET CONJECTURE AND MAXIMUM DIRECTED CUT IN CONNECTED DIGRAPH

- 2017

In this dissertation, we study the following two topics, i.e., the union closed set conjecture and the maximum edges cut in connected digraphs. The union-closed-set-conjecture-topic goes as follows.… Expand

New Conjectures for Union-Closed Families

- Mathematics, Computer Science
- Electron. J. Comb.
- 2016

It is shown that the optimal values the authors computed do not vary with $n, and special cases of the Frankl conjecture are proved, and new conjectures are proved that are not equivalent to it while still having wide-reaching implications if proven true. Expand

Union Closed Set Conjecture and Maximum Dicut in Connected Digraph

- Mathematics
- 2014

In this dissertation, we study the following two topics, i.e., the union closed set conjecture and the maximum edges cut in connected digraphs. The union-closed-set-conjecture-topic goes as follows.… Expand

Extremal Union-Closed Set Families

- Computer Science, Mathematics
- Graphs Comb.
- 2019

A lower bound of sizes of sets of a minimum counterexample to the dual version of the Union-Closed Sets Conjecture is obtained. Expand

Cutting Planes for Union-Closed Families

- Mathematics
- 2017

Frankl’s (union-closed sets) conjecture states that for any nonempty finite union-closed (UC) family of distinct sets there exists an element in at least half of the sets. Poonen’s Theorem… Expand

Cutting planes for families implying Frankl's conjecture

- Mathematics, Computer Science
- Math. Comput.
- 2020

A cutting-plane method is designed that computes the explicit weights which imply the existence conditions of Poonen’s Theorem and allows us to find a counterexample to a ten-year-old conjecture by R. Morris about the structure of generators for Non–FC-families. Expand

Polyhedral methods applied to extremal combinatorics problems

- Mathematics
- 2014

We study the polytopes describing two famous problems: the Turán hypergraph problem and the Frankl union-closed sets conjecture. The Turán hypergraph problem asks to find the maximum number of… Expand

Approximately counting locally-optimal structures

- Computer Science, Mathematics
- J. Comput. Syst. Sci.
- 2016

It is shown that various counting problems involving minimal separators are #SAT-hard to approximate, which has applications for constructing triangulations and phylogenetic trees. Expand

#### References

SHOWING 1-10 OF 37 REFERENCES

The union-closed sets conjecture almost holds for almost all random bipartite graphs

- Computer Science, Mathematics
- Eur. J. Comb.
- 2017

It is proved that, for every fixed edge-probability, almost every random bipartite graph almost satisfies Frankls conjecture. Expand

Union-Closed Families

- Mathematics, Computer Science
- J. Comb. Theory, Ser. A
- 1992

A number of equivalent conjectures are found and a general theorem stating exactly when a subfamily is enough to guarantee the existence of an element from the subfamily which is in half the sets of the whole family is proved. Expand

Graph generated union-closed families of sets

- Mathematics
- 1994

Let G be a graph with vertices V and edges E. Let F be the union-closed family of sets generated by E. Then F is the family of subsets of V without isolated points. Theorem: There is an edge e… Expand

A note on the union-closed sets conjecture

- Mathematics, Computer Science
- Australas. J Comb.
- 2010

It is shown that if q is the minimum cardinality of ∪A taken over all counterexamples A, then any countereXample A has cardinality at least 4q − 1. Expand

Claw-free graphs. III. Circular interval graphs

- Computer Science, Mathematics
- J. Comb. Theory, Ser. B
- 2008

This paper characterize the connected claw-free graphs G with a clique the deletion of which disconnects G into two parts both with at least two vertices by excluded induced subgraphs. Expand

A note on the union-closed sets conjecture

- Mathematics
- 1994

It has been conjectured that for any union-closed set there exists some element which is contained in at least half the sets in . It is shown that this conjecture is true if the number of sets in is… Expand

Representation characterizations of chordal bipartite graphs

- Mathematics, Computer Science
- J. Comb. Theory, Ser. B
- 2006

This work shows that a bipartite graph is chordal bipartites if and only if the complement is the intersection graph of a family of pairwise compatible claws in a weighted hypercircle. Expand

On the Union-Closed Sets Conjecture

- Mathematics
- 2017

Here are some notation and convention that we will adopt in this article: We use abbreviated notation for collections of sets of integers. For example, {{1, 2}, {1, 2, 3}, {3, 4}} denoted by {12,… Expand

The 11-element case of Frankl's conjecture

- Mathematics, Computer Science
- Electron. J. Comb.
- 2008

In 1979, P. Frankl conjectured that in a finite union-closed family of finite sets, there has to be an element that belongs to at least half of the sets in ${\cal F}$. Expand

Maximal independent sets in bipartite graphs obtained from Boolean lattices

- Computer Science, Mathematics
- Eur. J. Comb.
- 2011

Bounds are found on the numbers of maximal independent sets in bipartite graphs whose vertex sets are comprised of adjacent levels of the lattice and whose edges correspond to proper containment. Expand