Asymptotic study of the maximum number of edges in a uniform hypergraph with one forbidden intersection

被引:15
作者
Bobu, A. V. [1 ]
Kupriyanov, A. E. [1 ]
Raigorodskii, A. M. [1 ,2 ,3 ]
机构
[1] Moscow MV Lomonosov State Univ, Fac Mech & Math, Moscow, Russia
[2] State Univ, Moscow Inst Phys & Technol, Fac Innovat & High Technol, Dolgoprudnyi, Moscow Oblast, Russia
[3] Buryat State Univ, Inst Math & Comp Sci, Ulan Ude, Russia
基金
俄罗斯基础研究基金会;
关键词
hypergraphs with one forbidden intersection of edges; Frankl-Wilson Theorem; constant-weight error-correcting codes; Nelson-Hadwiger problem; CHROMATIC-NUMBERS; BORSUKS PROBLEM; THEOREM; DISTANCES; GRUNBAUM; SYSTEMS; CODES;
D O I
10.1070/SM8473
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
The object of this research is the quantity m(n, k, t) defined as the maximum number of edges in a k-uniform hypergraph possessing the property that no two edges intersect in t vertices. The case when k similar to k'n and t similar to t'n as n -> infinity, and k' is an element of (0, 1), t' is an element of (0, k') are fixed constants is considered in full detail. In the case when 2t < k the asymptotic accuracy of the Frankl-Wilson upper estimate is established; in the case when 2t >= k new lower estimates for the quantity m(n, k, t) are proposed. These new estimates are employed to derive upper estimates for the quantity A(n, 2 delta, omega), which is widely used in coding theory and is defined as the maximum number of bit strings of length n and weight omega having Hamming distance at least 2 delta from one another.
引用
收藏
页码:652 / 677
页数:26
相关论文
共 39 条
[11]   Independence numbers and chromatic numbers of some distance graphs [J].
Bobu, A. V. ;
Kostina, O. A. ;
Kupriyanov, A. E. .
PROBLEMS OF INFORMATION TRANSMISSION, 2015, 51 (02) :165-176
[12]  
BOLTYANSKI V. G., 1997, EXCURSIONS COMBINATO
[13]   INTERSECTION-THEOREMS WITH GEOMETRIC CONSEQUENCES [J].
FRANKL, P ;
WILSON, RM .
COMBINATORICA, 1981, 1 (04) :357-368
[14]   A COMPARISON OF SIGNALLING ALPHABETS [J].
GILBERT, EN .
BELL SYSTEM TECHNICAL JOURNAL, 1952, 31 (03) :504-522
[15]  
GRAHAM RL, 1990, WILEY INTERSCI SER D
[16]   ERROR DETECTING AND ERROR CORRECTING CODES [J].
HAMMING, RW .
BELL SYSTEM TECHNICAL JOURNAL, 1950, 29 (02) :147-160
[17]  
Klee V., 1991, DOLCIANI MATH EXP, V11
[18]   REALIZATION OF DISTANCES WITHIN SETS IN EUCLIDEAN SPACE [J].
LARMAN, DG ;
ROGERS, CA .
MATHEMATIKA, 1972, 19 (37) :1-&
[19]  
Levenshtein V. I., 1971, TRANSMISSION, V7, P281
[20]  
MacWilliams F.J., 1977, N HOLLAND MATH LIB, V16