Open Access
Access granted
Subscription Access
Vol 53, No 4 (2017)
- Year: 2017
- Articles: 7
- URL: https://journal-vniispk.ru/0032-9460/issue/view/10142
Coding Theory
Independence Numbers of Random Subgraphs of Some Distance Graph
Abstract
The distance graph G(n, 2, 1) is a graph where vertices are identified with twoelement subsets of {1, 2,..., n}, and two vertices are connected by an edge whenever the corresponding subsets have exactly one common element. A random subgraph Gp(n, 2, 1) in the Erd˝os–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 G1/2(n, 2, 1).
307-318
On the Number of Edges of a Uniform Hypergraph with a Range of Allowed Intersections
Abstract
We study the quantity p(n, k, t1, t2) 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 [t1, t2]. We present previously known upper and lower bounds on this quantity and analyze their interrelations. We obtain new bounds on p(n, k, t1, t2) 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.
319-342
343-348
Methods of Signal Processing
On Detection of Gaussian Stochastic Sequences
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 σ of signal vector intensities belongs to a given set ε. We investigate when it is possible to replace the set ε with a smaller set ε0 without loss of quality (and, in particular, replace it with a single point σ0).
349-367
On One Problem in Multichannel Signal Detection
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 kth channel with a known small prior probability π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.
368-380
Large Systems
Stochastic Operation Induced by Group Allocation of Particles and Generalized Branching Processes
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.
381-390
Quantifier Alternation in First-Order Formulas with Infinite Spectra
Abstract
The spectrum of a first-order formula is the set of numbers α 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 −α 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.
391-403