Delta-systems and qualitative (in)dependence

被引:4
作者
Körner, J [1 ]
Monti, A [1 ]
机构
[1] Univ Roma La Sapienza, Dept Comp Sci, I-00198 Rome, Italy
关键词
D O I
10.1006/jcta.2002.3256
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Following Erdos and Rado, three sets are said to form a delta triple if any two of them have the same intersection. Let F(n, 3) denote the largest cardinality of a family of subsets of an n-set not containing a delta-triple. It is not known whether lim sup(n-->lambda) n(-1) log F(n, 3) < 1. We say that a family of bipartitions of an n-set is qualitatively 3/4-weakly 3-dependent if the common refinement of any 3 distinct partitions of the family has at least 6 non-empty classes (i.e., at least 3/4 of the total). Let 1(n) denote the maximum cardinality of such a family. We derive a simple relation between the exponential asymptotics of F(n, 3) and I(n) and show, as a consequence, that lim sup(n-->lambda) n(-1) log F(n, 3) = 1 if and only if lim sup(n-->lambda) n(-1) log I(n) = 1. (C) 2002 Elsevier Science (USA).
引用
收藏
页码:75 / 84
页数:10
相关论文
共 14 条
[11]   RATIO OF OPTIMAL INTEGRAL AND FRACTIONAL COVERS [J].
LOVASZ, L .
DISCRETE MATHEMATICS, 1975, 13 (04) :383-390
[12]   ON QUALITATIVELY INDEPENDENT PARTITIONS AND RELATED PROBLEMS [J].
POLJAK, S ;
PULTR, A ;
RODL, V .
DISCRETE APPLIED MATHEMATICS, 1983, 6 (02) :193-205
[13]   ON THE MAXIMUM NUMBER OF QUALITATIVELY INDEPENDENT PARTITIONS [J].
POLJAK, S ;
TUZA, Z .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 1989, 51 (01) :111-116
[14]  
Renyi A., 1971, FDN PROBABILITY