pith. sign in

arxiv: math/9409215 · v1 · pith:VLGEQ6XZnew · submitted 1994-09-16 · 🧮 math.CO

Graph generated union-closed families of sets

classification 🧮 math.CO
keywords belongssetsunion-closedfamilyfamiliesgeneratedproofconjecture
0
0 comments X p. Extension
Add this Pith Number to your LaTeX paper What is a Pith Number?
\usepackage{pith}
\pithnumber{VLGEQ6XZ}

Prints a linked pith:VLGEQ6XZ badge after your title and writes the identifier into PDF metadata. Compiles on arXiv with no extra files. Learn more

read the original abstract

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 belongs to E such that |{U belongs to F | e belongs to U}| =< 1/2|F|. This is equivalent to the following assertion: If H is a union-closed family generated by a family of sets of maximum degree two, then there is an $x$ such that |{U belongs to H | x belongs to U}| > 1/2|H|. This is a special case of the union-closed sets conjecture. To put this result in perspective, a brief overview of research on the union-closed sets conjecture is given. A proof of a strong version of the theorem on graph-generated families of sets is presented. This proof depends on an analysis of the local properties of F and an application of Kleitman's lemma. Much of the proof applies to arbitrary union-closed families and can be used to obtain bounds on |{U belongs to F | e belongs to U}|/|F|.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.