A generalization of the Bollobas set pairs inequality

被引:3
作者
O'Neill, Jason [1 ]
Verstraete, Jacques [1 ]
机构
[1] Univ Calif San Diego, Dept Math, La Jolla, CA 92093 USA
关键词
GRAPH; HYPERGRAPH; FAMILIES; BOUNDS;
D O I
10.37236/9627
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
The Bollobas set pairs inequality is a fundamental result in extremal set theory with many applications. In this paper, for n >= k >= t >= 2, we consider a collection of k families A(i) : 1 <= i <= k where A(i) = {A(i,j) subset of [n] : j is an element of [n]} so that A(1),i(1) boolean AND ...boolean AND A(k,ik )not equal circle divide, if and only if there are at least t distinct indices i(1), i(2), ..., 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].
引用
收藏
页数:14
相关论文
共 26 条
[1]  
Alon N., 1985, EUR J COMBIN, V6, P211, DOI DOI 10.1016/S0195-6698(85)80029-9
[2]  
Bollob B., 1986, COMBINATORICS SET SY
[3]   ON GENERALIZED GRAPHS [J].
BOLLOBAS, B .
ACTA MATHEMATICA ACADEMIAE SCIENTIARUM HUNGARICAE, 1965, 16 (3-4) :447-&
[4]  
[Bondy J.A. [Lov77b] [Lov77b]], 1977, Graph Theory and Related Topics, P1
[5]   REPRESENTATION OF A GRAPH BY SET INTERSECTIONS [J].
ERDOS, P ;
GOODMAN, AW ;
POSA, L .
CANADIAN JOURNAL OF MATHEMATICS, 1966, 18 (01) :106-&
[6]   A PROBLEM IN GRAPH THEORY [J].
ERDOS, P ;
HAJNAL, A ;
MOON, JW .
AMERICAN MATHEMATICAL MONTHLY, 1964, 71 (10) :1107-&
[7]  
Frankl P., 1982, European J. Combin., V3, P125, DOI DOI 10.1016/S0195-6698(82)80025-5
[8]   Counting Intersecting and Pairs of Cross-Intersecting Families [J].
Frankl, Peter ;
Kupavskii, Andrey .
COMBINATORICS PROBABILITY & COMPUTING, 2018, 27 (01) :60-68
[9]   ON THE SIZE OF SEPARATING SYSTEMS AND FAMILIES OF PERFECT HASH FUNCTIONS [J].
FREDMAN, ML ;
KOMLOS, J .
SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1984, 5 (01) :61-68
[10]  
Furedi Z., 1984, Europ. J. Combin., V5, P133