RUS  ENG
Full version
JOURNALS // Problemy Peredachi Informatsii // Archive

Probl. Peredachi Inf., 2017 Volume 53, Issue 4, Pages 16–42 (Mi ppi2250)

This article is cited in 12 papers

Coding Theory

On the number of edges of a uniform hypergraph with a range of allowed intersections

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

a Department of Mathematical Statistics and Random Processes, Faculty of Mechanics and Mathematics, Lomonosov Moscow State University, Moscow, Russia
b Department of Innovation and High Technology, Moscow Institute of Physics and Technology (State University), Moscow, Russia
c Institute of Mathematics and Computer Science, Buryat State University, Ulan-Ude, Russia

Abstract: We study the quantity $p(n,k,t_1,t_2)$ equal to the maximum number of edges in a $k$-uniform hypergraph having the property that all cardinalities of pairwise intersections of edges lie in the interval $[t_1,t_2]$. We present previously known upper and lower bounds on this quantity and analyze their interrelations. We obtain new bounds on $p(n,k,t_1,t_2)$ and consider their possible applications in combinatorial geometry problems. For some values of the parameters we explicitly evaluate the quantity in question. We also give a new bound on the size of a constant-weight error-correcting code.

UDC: 621.391.1+519.1

Received: 27.01.2017
Revised: 25.06.2017


 English version:
Problems of Information Transmission, 2017, 53:4, 319–342

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025