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

作者：Bobu A V^*; Kupriyanov A E; Raigorodskii A M

来源：Sbornik: Mathematics , 2016, 207(5): 652-677.

DOI：10.1070/SM8473

• hypergraphs with one forbidden intersection of edges
• Frankl-Wilson Theorem
• constant-weight error-correcting codes
• Nelson-Hadwiger problem

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.

• 出版日期2016