Pith. sign in

REVIEW 2 cited by

Graph generated union-closed families of sets

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv math/9409215 v1 pith:VLGEQ6XZ submitted 1994-09-16 math.CO

classification math.CO
keywords belongssetsunion-closedfamilyfamiliesgeneratedproofconjecture
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
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|.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Frequent elements in union-closed set families

    math.CO 2024-12 reject novelty 8.0 of 10

    The k-th most frequent element in any union-closed set family appears in at least 1/(2^{k-1}+1) of the sets, with equality only for the near-k-cube families.

  2. Redundancy Is All You Need (for CSP Sparsification)

    cs.DS 2024-11 unverdicted novelty 8.0 of 10

    For any CSP predicate R, unweighted CSP(R) instances admit sparsifiers of size at most their non-redundancy (up to polylog factors); weighted cases are pinned to chain length, via a VC-type theorem for set families us...

Pith tools