PROBLEMS OF INFORMATION TRANSMISSION
A translation of Problemy Peredachi Informatsii

CONTENTS                  

Independence Numbers of Random Subgraphs of Some Distance Graph
N. M. Derevyanko and S. G. Kiselev
pp. 307–318

Abstract—The distance graph $G(n,2,1)$ is a graph where vertices are identified with two-element subsets of $\{1, 2,\ldots,n\}$, and two vertices are connected by an edge whenever the corresponding subsets have exactly one common element. A random subgraph $G_p(n,2,1)$ in the Erdős–Rényi model is obtained by selecting each edge of $G(n,2,1)$ with probability $p$ independently of other edges. We find a lower bound on the independence number of the random subgraph $G_{1/2}(n,2,1)$.

On the Number of Edges of a Uniform Hypergraph with a Range of Allowed Intersections
A. V. Bobu, A. E. Kupriyanov, and A. M. Raigorodskii
pp. 319–342

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.

On Spectra of Linear Codes
V. K. Leont'ev
pp. 343–348

Abstract—We present new MacWilliams-type identities for spectra of linear codes.

On Detection of Gaussian Stochastic Sequences
M. V. Burnashev
pp. 349–367

Abstract—We consider the minimax detection problem for a Gaussian random signal vector in white Gaussian additive noise. It is assumed that an unknown vector $\boldsymbol{\sigma}$ of signal vector intensities belongs to a given set $\mathcal{E}$. We investigate when it is possible to replace the set $\mathcal{E}$ with a smaller set $\mathcal{E}_0$ without loss of quality (and, in particular, replace it with a single point $\boldsymbol{\sigma}_0$).

On One Problem in Multichannel Signal Detection
E. V. Burnaev and G. K. Golubev
pp. 368–380

Abstract—We consider a statistical problem of detecting a signal with unknown energy in a multichannel system, observed in a Gaussian noise. We assume that the signal can appear in the $k$th channel with a known small prior probability $\bar{\pi}_k$. Using noisy observations from all channels, we would like to detect whether the signal is presented in one of the channels or we observe pure noise. We describe and compare statistical properties of the maximum posterior probability test and optimal Bayes test. In particular, for these tests we obtain limiting distributions of test statistics and define sets of their undetectable signals.

Stochastic Operation Induced by Group Allocation of Particles and Generalized Branching Processes
A. V. Lebedev
pp. 381–390

Abstract—We introduce a stochastic operation induced by group allocation of particles in cells, which belongs to the class of Archimedean operations. We analyze its properties and prove limit theorems. We also introduce and study branching processes with this operation, which can describe various phenomena in biological populations and computer networks, including virus propagation. In the limit, a nonlinear dynamical system occurs.

Quantifier Alternation in First-Order Formulas with Infinite Spectra
M. E. Zhukovskii
pp. 391–403

Abstract—The spectrum of a first-order formula is the set of numbers $\alpha$ such that for a random graph in a binomial model where the edge probability is a power function of the number of graph vertices with exponent $-\alpha$ the truth probability of this formula does not tend to either zero or one. In 1990 J. Spenser proved that there exists a first-order formula with an infinite spectrum. We have proved that the minimum quantifier depth of a first-order formula with an infinite spectrum is either 4 or 5. In the present paper we find a wide class of first-order formulas of depth 4 with finite spectra and also prove that the minimum quantifier alternation number for a first-order formula with an infinite spectrum is 3.