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

A. V. Bobu ; A. E. Kupriyanov ; A. M. Raigorodskii

Sbornik. Mathematics, Tome 207 (2016) no. 5, pp. 652-677

Résumé

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\sim k'n$ and $t \sim t'n$ as $n \to \infty$, and $k' \in (0,1)$, $t' \in (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 \geqslant 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. Bibliography: 38 titles.

Détail

Keywords: hypergraphs with one forbidden intersection of edges, Frankl-Wilson Theorem, constant-weight error-correcting codes, Nelson-Hadwiger problem.