RUS  ENG
Full version
JOURNALS // Matematicheskii Sbornik // Archive

Mat. Sb., 2016 Volume 207, Number 5, Pages 17–42 (Mi sm8473)

This article is cited in 19 papers

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

A. V. Bobua, A. E. Kupriyanova, A. M. Raigorodskiiabc

a Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
b Buryat State University, Institute for Mathematics and Informatics, Ulan-Ude
c Department of Innovations and High Technology, Moscow Institute of Physics and Technology

Abstract: 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.

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

UDC: 519.112.74+519.176

MSC: Primary 05C15, 05C35; Secondary 63R10, 90C27

Received: 12.01.2015 and 18.01.2016

DOI: 10.4213/sm8473


 English version:
Sbornik: Mathematics, 2016, 207:5, 652–677

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024