|
This article is cited in 19 scientific papers (total 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.
Received: 12.01.2015 and 18.01.2016
Citation:
A. V. Bobu, A. E. Kupriyanov, A. M. Raigorodskii, “Asymptotic study of the maximum number of edges in a uniform hypergraph with one forbidden intersection”, Sb. Math., 207:5 (2016), 652–677
Linking options:
https://www.mathnet.ru/eng/sm8473https://doi.org/10.1070/SM8473 https://www.mathnet.ru/eng/sm/v207/i5/p17
|
Statistics & downloads: |
Abstract page: | 714 | Russian version PDF: | 202 | English version PDF: | 32 | References: | 75 | First page: | 51 |
|