Makarov, G.D.
Published in
Discrete Mathematics and Applications

The paper is devoted to the relation between random trees and branching processes for which the number of descendants of one particle has the Poisson distribution. The main result of the paper consists in finding the leading term of the asymptotics of the probabilities of large deviations for the height of a random tree. Similar problems were consi...

Bardakov, V. G.
Published in
Discrete Mathematics and Applications

We prove Brenner-Evans' conjecture that, for any natural numbers k ≥ 4 and m ≥ 1, any even permutation of the group Akm is a product of two permutations, each of them is expanded into a product of m independent cycles of length k. It is known that this assertion is incorrect for k = 2, 3.

Sachkov, V.N. Oshkin, I.B.
Published in
Discrete Mathematics and Applications

A square non-negative matrix is called primitive if all the elements of some power of this matrix are positive. The exponent of a primitive matrix is the minimum power satisfying this condition. The exponent of a class of primitive matrices is the minimum power such that all the matrices of the class to this power have positive elements only. In th...

Gordeev, E.N. Tarastsov, O.G.
Published in
Discrete Mathematics and Applications

For the past decade the Steiner minimal tree problem has attracted the attention of researchers in discrete optimization. A brief survey of the main results concerning the properties and algorithms of the Steiner problem in the Euclidean plane, the Steiner problem in the plane with rectilinear metric and the Steiner problem in networks is done in t...

Maximov, V.M.
Published in
Discrete Mathematics and Applications

Some subgroups of automorphisms of Grassmann's algebra and their explicit descriptions are considered. The notion of a graduated determinant is introduced and its properties are investigated.

Levin, A.G. Tyshkevich, R.I.
Published in
Discrete Mathematics and Applications

The notion of the line hypergraph is introduced. It is an immediate generalization of two wellknown objects: a line graph and a dual hypergraph. We obtain various characterizations of line hypergraphs; we also obtain a generalization of Whitney's theorem. The NP-completeness of the problem of determining whether a given graph is the line graph of a...

Timashev, A.N.
Published in
Discrete Mathematics and Applications

Theorems on large deviations in the polynomial scheme of trials with a fixed number of outcomes and a growing number of trials, which generalize the analogous known results for the case of binomial scheme, are obtained.

Irmatov, A.A.
Published in
Discrete Mathematics and Applications

A Boolean function is called a threshold function if its truth domain is a part of the n-cube cut off by some hyperplane. The number of threshold functions of n variables P(2, n) was estimated in [1, 2, 3]. Obtaining the lower bounds is a problem of special difficulty. Using a result of the paper [4], Zuev in [3] showed that for sufficiently large ...

Kuzmin, O.V. Leonova, O.V.
Published in
Discrete Mathematics and Applications

We consider the Touchard polynomials, which are extensions of the Bell polynomials, and the P-polynomials which, together with the Touchard polynomials, form a quasi-orthogonal system. We establish analytical conjugacy of the Touchard polynomials and the P-polynomials, which allows us, in particular, to find a series of new recurrence relations for...

Sevastyanov, B.A.
Published in
Discrete Mathematics and Applications

Any modified branching process ℬ* is constructed by means of two Galton-Watson processes ℬ0, ℬ1, and a fixed finite set S of positive integers. The number of particles μ*(t) of the process ℬ* at time instants t = 0, 1, 2, ... evolves as follows. If μ*(t) ∈ S, then each of the μ*(t) particles independently of each other produces an offspring accordi...