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 条
[1]  
CSISZAR I, 1981, INFORMATION THEORY C
[2]  
DEUBER WA, 1995, J COMBIN THEORY SE A, V79, P118
[3]   FAMILIES OF FINITE SETS IN WHICH NO SET IS COVERED BY THE UNION OF 2 OTHERS [J].
ERDOS, P ;
FRANKL, P ;
FUREDI, Z .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 1982, 33 (02) :158-166
[4]   COMBINATORIAL PROPERTIES OF SYSTEMS OF SETS [J].
ERDOS, P ;
SZEMEREDI, E .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 1978, 24 (03) :308-313
[5]   SPERNER CAPACITIES [J].
GARGANO, L ;
KORNER, J ;
VACCARO, U .
GRAPHS AND COMBINATORICS, 1993, 9 (01) :31-46
[6]   CAPACITIES - FROM INFORMATION-THEORY TO EXTREMAL SET-THEORY [J].
GARGANO, L ;
KORNER, J ;
VACCARO, U .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 1994, 68 (02) :296-316
[7]   SUBCUBE FAULT-TOLERANCE IN HYPERCUBES [J].
GRAHAM, N ;
HARARY, F ;
LIVINGSTON, M ;
STOUT, QF .
INFORMATION AND COMPUTATION, 1993, 102 (02) :280-314
[8]  
Kleitman D. J., 1973, Discrete Mathematics, V6, P255, DOI 10.1016/0012-365X(73)90098-8
[9]  
KORNER J, 1995, J COMBIN THEORY SE A, V71, P12
[10]  
Kostochka AV, 2000, NUMBERS, INFORMATION AND COMPLEXITY, P143