A generalization of the Bollobás set pairs inequality
Preprint
Abstract
The Bollob\'as set pairs inequality is a fundamental result in extremal set theory with many applications. In this paper, for $n \geq k \geq t \geq 2$, we consider a collection of $k$ families $\mathcal{A}_i: 1 \leq i \leq k$ where $\mathcal{A}_i = \{ A_{i,j} \subset [n] : j \in [n] \}$ so that $A_{1, i_1} \cap \cdots \cap A_{k,i_k} \neq \emptyset $ if and only if there are at least $t$ distinct indices $i_1,i_2,\dots,i_k$. Via a natural connection to a hypergraph covering problem, we give bounds on the maximum size $\beta_{k,t}(n)$ of the families with ground set $[n]$.
Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Counting Intersecting and Pairs of Cross-Intersecting FamiliesCombinatorics, Probability and Computing, 2017
- Exact bounds for some hypergraph saturation problemsJournal of Combinatorial Theory, Series B, 2015
- New Bounds for Perfect Hashing via Information TheoryEuropean Journal of Combinatorics, 1988
- A Simple Proof of the Upper Bound TheoremEuropean Journal of Combinatorics, 1985
- On the Size of Separating Systems and Families of Perfect Hash FunctionsSIAM Journal on Algebraic Discrete Methods, 1984
- An Extremal Problem for two Families of SetsEuropean Journal of Combinatorics, 1982
- Contentment in graph theory: Covering graphs with cliquesIndagationes Mathematicae, 1977
- Solution of a problem of A. Ehrenfeucht and J. MycielskiJournal of Combinatorial Theory, Series A, 1974
- The Representation of a Graph by Set IntersectionsCanadian Journal of Mathematics, 1966