Bollobás-type inequalities on set $k$-tuples
Preprint
Abstract
The Bollob\'as set pairs inequality is a fundamental result in extremal set theory. In this paper, we examine suitable conditions on $k$-wise intersections from a $k$-tuple of set families for which a Bollob\'as-type inequality holds. We then use the standard connection between extremal set theory and covering problems to give lower and upper bounds on the biclique covering numbers of a few particular $k$-uniform hypergraphs. We also provide random and explicit constructions of these Bollob\'as set $k$-tuples.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