Union-free hypergraphs and probability theory
type: Item
instance of: scholarly article
title: Union-free hypergraphs and probability theory
zbMATH Open document ID: 0546.05049
DOI: 10.1016/S0195-6698(84)80025-6
author: Zoltán Füredi
author: Peter Frankl
published in: European Journal of Combinatorics
publication date: 1984-01-01T00:00:00Z
review text: This paper contains new lower and upper bounds on the number of subsets of an n element set one can have so that the union of no two equals that of two others. A new lower bound is obtained when no two unions of any kind are the same; and a new upper bound when no set has the same union with two others. Related problems when the sets have size restrictions are reviewed and some new results obtained. The lower bounds are obtained by probabilistic reasoning, while one upper bound uses an entropy argument and the other follows by an induction.
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 60C05
zbMATH DE Number: 3869378
zbMATH Keywords: maximum number of distinct subsets
reviewed by: Daniel J. Kleitman
MaRDI profile type: Publication
cites work: Sidon sets in groups and induced subgraphs of Cayley graphs
cites work: Three-graphs without two triples whose symmetric difference is contained in a third
cites work: Q5771387
cites work: A new extremal property of Steiner triple-systems
cites work: Union-free families of sets and equations over fields
cites work: Graphs without quadrilaterals
cites work: Q4052170
cites work: Intersections of k-element sets
cites work: Q4156696
cites work: Q5781249
full work available at URL: s0195-6698(84)80025-6
OpenAlex ID: W2146586570
Recommended article: On the structure of random hypergraphs
Recommended article: Lower bounds for the probability of a union via chordal graphs
Recommended article: On the upper tail problem for random hypergraphs
Recommended article: On the probability of union in the $n$-space
Recommended article: Dirac-type theorems in random hypergraphs
Recommended article: Graph-based upper bounds for the probability of the union of events
Recommended article: On the probability of independent sets in random graphs
Recommended article: On the Choice Number of Random Hypergraphs
Recommended article: On the decomposition of random hypergraphs
Recommended article: Upper bounds for the probability of a union by multitrees
description: scientific article; zbMATH DE number 3869378