Том 215, № 6 (2016)

We describe a new combinatorial-algebraic transformation on graphs which we call “chip removal.” It generalizes the well-known Urban Renewal trick of Propp and Kuperberg. The chip removal is useful in calculations of determinants of adjacency matrices and matching numbers of graphs. A beautiful example of this technique is a theorem on removing four-contact chips, which generalizes Kuo’s graphical condensation method. Numerous examples are given. Bibliography: 10 titles.

We study the noncommutative operator graph ℒ_θdepending on a complex parameter θ recently introduced by M. E. Shirokov to construct channels with positive quantum zero-error capacity having vanishing n-shot capacity. We define a noncommutative group G and an algebra A_θwhich is the quotient of ℂG by a special algebraic relation depending on θ such that the matrix representation ϕ of A_θresults in the algebra ℳ_θgenerated by ℒ_θ. In the case of θ = ±1, the representation ϕ degenerates into a faithful representation of ℂK₄, where K₄is the Klein group. Thus, ℒ_θcan be regarded as a noncommutative deformation of the graph associated with the Klein group. Bibliography: 16 titles.

We prove that for ergodic automorphisms of a Lebesgue space, the definition of the measure-theoretic entropy suggested in the master thesis by D. Arov (1957) and remained unpublished and the well-known definition of Sinai (1959) reduce to each other, while in general this is not the case.

It is well known that large random structures may have nonrandom macroscopic properties. We give an example of nonrandom properties for a class of large optimization problems related to the computational problem MAXFLS= of calculating the maximum number of consistent equations in a given overdetermined system of linear equations. A problem of this kind is faced by a decision maker (an Agent) choosing means to protect a house from natural disasters. For this class we establish the following. There is no “efficiently computable” optimal strategy of the Agent. As the size of a random instance of the optimization problem goes to infinity, the probability that the uniform mixed strategy of the Agent is ε-optimal goes to one. Moreover, there is no “efficiently computable” strategy of the Agent that is substantially better for each instance of the optimization problem. Bibliography: 13 titles.

We prove that if a measure-preserving automorphism has a scaling entropy sequence, then this sequence can be chosen nondecreasing and subadditive.

Let \( \mathbb{G} \) be the group of automorphisms of a free group F_∞ of infinite order. Let ℍ be the stabilizer of the first m generators of F_∞. We show that the double cosets Γ_m = ℍ \ \( \mathbb{G} \)/ℍ admit a natural semigroup structure. For any compact group K, the semigroup Γ_m acts in the space L on the product of m copies of K. Bibliography: 20 titles.

Consider a computational algebraic problem with inputs depending on parameters. The aim of the computation is to stratify the variety of parameters so that for each stratum \( {\mathcal{W}}_{\alpha } \), for arbitrary values of the parameters from \( {\mathcal{W}}_{\alpha } \), the solution of the problem as a function of the parameters is computed by the same algebraic formulas depending only on the stratum \( {\mathcal{W}}_{\alpha } \). We suggest a model for computations with parameters which is convenient for practical purposes and prove a fundamental result for it.