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 条
[1]  
Agarwal P. K., 1995, WILEY INTERSCI SER D
[2]   The complete intersection theorem for systems of finite sets [J].
Ahlswede, R ;
Khachatrian, LH .
EUROPEAN JOURNAL OF COMBINATORICS, 1997, 18 (02) :125-136
[3]   The complete nontrivial-intersection theorem for systems of finite sets [J].
Ahlswede, R ;
Khachatrian, LH .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 1996, 76 (01) :121-138
[4]  
Ahlswede R, 2008, UNIVERSITEXT, P1
[5]  
[Anonymous], 2013, Thirty Essays on Geometric Graph Theory, DOI [10.1007/978-1-4614-0110-0_23, DOI 10.1007/978-1-4614-0110-0_23]
[6]  
[Anonymous], 2009, The mathematical coloring book. Mathematics of coloring and the colorful life of its creators
[7]  
[Anonymous], 1944, Portugal. Math.
[8]  
[Anonymous], 2008, Surveys in contemporary mathematics, London Math. Soc. Lecture Note Ser.
[9]   Codes with forbidden distances [J].
Bassalygo, L ;
Cohen, G ;
Zémor, G .
DISCRETE MATHEMATICS, 2000, 213 (1-3) :3-11
[10]  
Bassalygo L. A., 1965, Problems of Information Transmission, V1, P32