Search

It is shown that an approach earlier used by the author for classification of closed simply connected 6-manifolds (reduction to the problem of calculating certain bordism groups) can also be applied for easily obtaining the results by Barden (1965) on classification of closed simply connected 5-manifolds. Bibliography: 11 titles.

The present paper is devoted to graph-links with many components and consists of two parts. In the first part of the paper we classify vertices of a labeled graph according to the component they belong to. Using this classification, we construct an invariant of graph-links. This invariant shows that the labeled second Bouchet graph generates a nonrealizable graph-link. In the second part of the work we introduce the notion of an oriented graph-link. We define a writhe number for the oriented graph-link and we get an invariant of oriented graph-links, the Jones polynomial, by normalizing the Kauffman bracket with the writhe number.

Let $X,X_1,\ldots,X_n$ be independent identically distributed random variables. The paper deals with the question about the behavior of the concentration function of the random variable $\sum\limits_{k=1}^{n}X_k a_k$ according to the arithmetic structure of vectors $a_k$. Recently, the interest to this question has increased significantly due to the study of distributions of eigenvalues of random matrices. In this paper we formulate and prove multidimensional generalizations of the results Eliseeva and Zaitsev (2012). They are also the refinements of the results of Friedland and Sodin (2007) and Rudelson and Vershynin (2009)., Comment: 13 pages

The Q-index of a simple graph is the largest eigenvalue of its signless Laplacian, or Q-matrix. In our previous paper [1] we gave three lower and three upper bounds for the Q-index of nested split graphs, also known as threshold graphs. In this paper, we give another two upper bounds, which are expressed as solutions of cubic equations (in contrast to quadratics from [1]). Some computational results are also included.

This paper deals with an extremal problem concerning hypergraph colorings. Let k be an integer. The problem is to find the value mk(n) equal to the minimum number of edges in an n-uniform hypergraph not admitting two-colorings of the vertex set such that every edge of the hypergraph contains k vertices of each color. In this paper, we obtain the exact values of m2(5) and m2(4), and the upper bounds for m3(7) and m4(9).

In this paper, we consider structured automata without output signals whose state sets are endowed with an algebraic structure of hypergraphs. The main result of the paper is a theorem where we obtain necessary and sufficient conditions for the possibility of defining on the state set of some automaton A a structure of a hypergraph H such that the automaton A will be the universal hypergraphic automaton.

This paper is a follow-up to a previous paper where the logical characterization of n-ary synchronous relations due to Eilenbeig, Elgot, and Shepherdson was investigated in the case where the alphabet has infinitely many letters. Here we show that modifying one of the predicates leads to a completely different picture for infinite alphabets, though it does not change the expressive power for finite alphabets. Indeed, roughly speaking, being able to express the fact that two words end with the same symbol leads to an undecidable theory, already for the Σ2 fragment. Finally, we show that the existential fragment is decidable. Bibliography: 19 titles.

Let A be a class of Abelian groups, A ∈ A, and End(A) be the additive endomorphism group of the group A. The group A is said to be defined by its endomorphism group in the class {ie208-01} if for every group B ∈ B such that End(B) ≅ End(A) the isomorphism B ≅ A holds. The paper considers the problem of definability of a periodic Abelian group A such that End-End(A) ≅ End(A). The classes of periodical Abelian groups, of divisible Abelian groups, of reduced Abelian groups, of nonreduced Abelian groups, and of all Abelian groups are investigated in this paper.

This paper compares sequences of independent, mean zero random variables in a rearrangement-invariant space X on [0, 1] with sequences of disjoint copies of individual terms in the corresponding rearrangement-invariant space Z X 2 on [0, ∞). The principal results of the paper show that these sequences are equivalent in X and Z X 2 , respectively, if and only if X possesses the (so-called) Kruglov property. We also apply our technique to complement well-known results concerning the isomorphism between rearrangement-invariant spaces on [0, 1] and [0, ∞). Bibliography: 20 titles.

A new method, which enables us to compute rather efficiently the Galois group of a polynomial over ℚ or over ℤ, is presented. Reductions of this polynomial with respect to different prime modules are studied, and the information obtained is used for the calculation of the Galois group of the initial polynomial. This method uses an original modification of the Chebotarev density theorem, and it is in essence a probabilistic method. The irreducibility of the polynomial under consideration is not assumed. The appendix to this paper contains tables, which enable us to find the Galois group of polynomials of degree less than or equal to 10 as a subgroup of the symmetric group. Here the final part of the paper is published. The first part is contained in a previous issue (see Vol. 134, No. 6 (2006)). Bibliography: 10 titles.

A. A. Tuganbaev UDC 512.55All rings are assumed to be associative and to have a nonzero identity element. Let A be a ring,and let M be a rightA-module. A proper ideal P ofthe ringA is said to be right primitive if P is theannihilator ofa simple rightA-module (i.e., ifthere exists a maximal right idealB ofthe ringA suchthat P is the largest ideal of A contained in B). Consequently, every maximal ideal is a right and leftprimitive ideal. A submodule N ofthe moduleM is said to be primitively pure (resp. maximally pure)ifNP = NMP for every right primitive (resp. maximal) idealP ofthe ringA. A module M is said tobe primitively divisible (resp. maximally divisible)ifM = MP for every right primitive (resp. maximal)ideal P ofthe ringA.AringA is called a right max ring ifevery nonzero rightA-module has a maximalsubmodule. Maximally pure submodules and maximally divisible modules are studied in [3,4,6,7]. In [5],right max rings with polynomial identity are described. In [10], right quasi-invariant right max rings aredescribed.The main results ofthis paper are Theorems 1 and 2.Theorem1. Let A be either a P.I. ring or a right quasi-invariant ring. Then the following conditionsare equivalent.(1) A is a regular ring.(2) All submodules of any right A-module are primitively pure.(3) All submodules of any right A-module are maximally pure.(4) All principal right ideals of the ring A are primitively pure.(5) All principal right ideals of the ring A are maximally pure.Remark1. Let A be a simple ring. It is obvious that all submodules ofanyA-module M are maximallypure and primitively pure in M. Since the ring A is not necessarily regular, Theorem 1 does not hold forarbitrary rings.Theorem2. For a P.I. ring A,the following conditions are equivalent.(1) All prime ideals of the ring A are maximal ideals,andJ(A) is a right or left t-nilpotent ideal.(2) There do not exist nonzero primitively divisible right A-modules.(3) There do not exist nonzero primitively divisible left A-modules.(4) There do not exist nonzero maximally divisible right A-modules.(5) There do not exist nonzero maximally divisible left A-modules.(6) A is a right max ring.(7) A is a left max ring.The paper also contains some other assertions on primitively (resp. maximally) pure submodulesand primitively (resp. maximally) divisible modules.The proofs of Theorems 1 and 2 are decomposed into a series of lemmas. We present the necessarynotation and definitions. For a module M,theJacobson radical of M is denoted by J(M). For a moduleM and its subset X,wedenotebyr(X) the annihilator of X. For a module M, a submodule N ofM is said to be essential if NX = 0 for every nonzero submoduleX ofthe moduleM.AringA issaid to be regular if a ∈ aAa for each element a ∈ A.AringA is said to be right quasi-invariant if

In this paper, we introduce a novel polynomial-time algorithm to compute graph invariants based on the idea of a modified random walk on graphs. Though not proved to be a full graph invariant yet, our method gives the right answer for the graph instances other well-known methods could not compute (such as special Furer gadgets and point-line incidence graphs of finite projective planes of higher degrees).

The minimality theorem states, in particular, that on cohomology H(A) of a dg algebra there exists sequence of operations mi : H(A)⊗i → H(A), i = 2, 3, . . . , which form a minimal A ∞ -algebra (H(A), {m i }). This structure defines on the bar construction BH(A) a correct differential dm so that the bar constructions (BH(A), d m ) and BA have isomorphic homology modules. It is known that if A is equipped additionally with a structure of homotopy Gerstenhaber algebra, then on BA there is a multiplication which turns it into a dg bialgebra. In this paper, we construct algebraic operations Ep,q : H(A) ⊗p ⊗H(A) ⊗q → H(A), p, q = 0, 1, 2, . . ., which turn (H(A), {m i }, {E p,q }) into a B ∞ -algebra. These operations determine on BH(A) correct multiplication, so that (BH(A), d m ) and BA have isomorphic homology algebras.

In this paper, we give new upper bounds for the chromatic numbers for integer lattices and some rational spaces and other lattices. In particular, we have proved that for any concrete integer number d, the chromatic number of ℤn with critical distance \( \sqrt{2d} \) has a polynomial growth in n with exponent less than or equal to d (sometimes this estimate is sharp). The same statement is true not only in the Euclidean norm, but also in any lp norm. Moreover, we have given concrete estimates for some small dimensions as well as upper bounds for the chromatic number of ℚpn, where by ℚp we mean the ring of all rational numbers having denominators not divisible by some prime numbers.

Many invariants of knots rely upon smoothing the knot at its crossings. To compute them, it is necessary to know how to count the number of connected components the knot diagram is broken into after the smoothing. In this paper, it is shown how to use a modification of a theorem of Zulli together with a modification of the spectral theory of graphs to approach such problems systematically. We give an application to counting subdiagrams of pretzel knots which have one component after oriented and unoriented smoothings.

The paper presents estimates of small deviation probabilities of the sum $$ {\displaystyle \sum_{j\ge 1}{\leftthreetimes}_j{X}_j} $$ , where {⋋j} are positive numbers and {Xj} are i.i.d. positive random variables satisfying weak restrictions at zero and infinity. Bibliography: 16 titles.

Let L be the Laplace matrix of a weighted digraph. The aim of the paper is to establish a simple way for computing any coefficient of the characteristic polynomial of L as a constant sign sum over the incoming spanning forests. The idea is to express L as the product of generalized (weighted) incidence matrices. It turns out that the minors of them can be studied in terms of the tree-like structure of the digraph. This makes it possible to compute the minors of L.

For every real number γ ≥ 1 we denote by K↓(γ) the least possible value of the constant term of an even nonnegative trigonometric polynomial with monotone coefficients such that all its coefficients, save for the constant term, are not lesser than 1 and the sum of these coefficients equals γ. In this paper, the asymptotic estimate of K↓(γ) is found and some extremal problems on the minimum of the constant term of an even nonnegative trigonometric polynomial are studied.

In this paper, we prove the decidability of the ultimate periodicity problem (the HD0L periodicity problem).

Let \( \mathbb{F} \) be a linearly ordered field. Consider Gn(\( \mathbb{F} \)), which is the subsemigroup of GLn(\( \mathbb{F} \)) consisting of all matrices with nonnegative coefficients. In 1940, A. I. Maltsev introduced the concept of the group of fractions for a semigroup. In the given paper, we prove that the group of fractions of G3(\( \mathbb{F} \)) coincides with GL3(\( \mathbb{F} \)).

This paper deals with extremal problems concerning colorings of partial Steiner systems. We establish a new sufficient condition for r-colorability of a hypergraph from some class of such systems in terms of maximum vertex degree. Moreover, as a corollary we obtain a new lower bound for the threshold probability for r-colorability of a random hypergraph in a binomial model.

Let the vertices of a circle graph be divided into several groups. This paper contains lower bounds on the size of an independent set that can be contained in one group of this subdivision. Bibliography: 7 titles.

In this paper, we consider so-called double covering polytopes. In 1995, Matsui showed that the problem of checking nonadjacency on these polytopes is NP-complete. We show that double covering polytopes are faces of the following polytopes: knapsack polytopes, set covering polytopes, cubic subgraph polytopes, 3-SAT polytopes, partial order polytopes, traveling salesman polytopes, and some others.

In this paper, we define coherent morphisms of chain maps and homology groups of morphisms of this type. We construct strong homology groups of continuous maps of compact metric spaces and prove that for each continuous map f : X → Y , there exists a long exact homological sequence. Moreover, we show that for each inclusion i : A → X of compact metric spaces, there exists an isomorphism $ {{\bar{H}}_n}(i)\approx {{\bar{H}}_n}\left( {X,A} \right) $ .

Let \( \mathbb{F} \) be a finite field of characteristics different from 2. We show that no bijective map transforms the permanent to the determinant when the cardinality of \( \mathbb{F} \) is sufficiently large. Also we determine Gibson barriers (the maximal and minimal numbers of nonzero elements) for convertible (0, 1)-matrices and solve several related problems in different matrix subspaces. Our results are illustrated by examples. This paper is based on the joint work with G. Dolinar, B. Kuzma, and M. Orel.

Consider a projective algebraic variety W that is an irreducible component of the set of all common zeros of a family of homogeneous polynomials of degree less than d in n + 1 variables in zero characteristic. Consider a linear system on W given by homogeneous polynomials of degree d'. Under the conditions of the first Bertini theorem for W and this linear system, we show how to construct an irreducible divisor in general position from the statement of this theorem. This algorithm is deterministic and polynomial in (dd′)n and the size of the input. This paper is the second part in a tree-part series. Bibliography: 21 titles.

This paper is devoted to subexponential estimates in Shirshov’s height theorem. A word W is n-divisible if it can be represented in the form W = W0W1⋯Wn, where W1 ≺ W2 ≺⋯≺ Wn. If an affine algebra A satisfies a polynomial identity of degree n, then A is spanned by non-n-divisible words of generators a1 ≺⋯≺ al. A. I. Shirshov proved that the set of non-n-divisible words over an alphabet of cardinality l has bounded height h over the set Y consisting of all words of degree ≤ n − 1. We show that h < Φ (n, l), where Φ(n, l) = 287l∙n12 log3 n+48. Let l, n, and d ≥ n be positive integers. Then all words over an alphabet of cardinality l whose length is greater than ψ(n, d, l) are either n-divisible or contain the dth power of a subword, where ψ(n, d, l) = 218l(nd)3 log3(nd)+13d2. In 1993, E. I. Zelmanov asked the following question in the Dniester Notebook: Suppose that F2,m is a 2-generated associative ring with the identity xm = 0. Is it true that the nilpotency degree of F2,m has exponential growth? We give the definitive answer to E. I. Zelmanov by this result. We show that the nilpotency degree of the l-generated associative algebra with the identity xd = 0 is smaller than ψ(d, d, l). This implies subexponential estimates on the nilpotency index of nil-algebras of arbitrary characteristic. Shirshov’s original estimate was just recursive; in 1982 a double exponent was obtained, and an exponential estimate was obtained in 1992. Our proof uses Latyshev’s idea of an application of the Dilworth theorem. We think that Shirshov’s height theorem is deeply connected to problems of modern combinatorics. In particular, this theorem is related to the Ramsey theory. We obtain lower and upper estimates of the number of periods of length 2, 3, n − 1 in some non-n-divisible word. These estimates differ only by a constant.

In the paper, the scheme of independent particle allocation is considered. A connection is demonstrated between finite-dimensional distributions for the process of the number of particles assigned to the k-th cell and the conditional distribution of independent Poisson distributed random variables. Conditions are specified for the convergence of these distributions to finite-dimensional distributions of the Gaussian process. A certain scheme of dependent particle allocation on a countable set of cells is introduced and investigated.

This paper studies the problem on the frequency of the event where a graph with a fixed number of vertices contains induced subgraphs that are isomorphic to distance graphs in spaces of definite dimensions. In particular, the case of plane and three-dimensional spaces is considered.

In this paper, we describe automorphisms of the lattice \( {\mathbb A} \) of all subalgebras of the semiring ℝ+[x] of polynomials in one variable over the semifield ℝ+ of nonnegative real numbers. It is proved that any automorphism of the lattice A is generated by an automorphism of the semiring ℝ+[x] that is induced by a substitution x ⟼ px for some positive real number p. It follows that the automorphism group of the lattice \( {\mathbb A} \) is isomorphic to the group of all positive real numbers with multiplication. A technique of unigenerated subalgebras is applied.

We define the length of a finite system of generators of a given algebra \( \mathcal{A} \) as the smallest number k such that words of length not greater than k generate \( \mathcal{A} \) as a vector space, and the length of the algebra is the maximum of the lengths of its systems of generators. In this paper, we obtain a classification of matrix subalgebras of length 1 up to conjugation. In particular, we describe arbitrary commutative matrix subalgebras of length 1, as well as those that are maximal with respect to inclusion.

In this paper, we obtain an upper estimate for the cardinality of a subset of the discrete torus over a field of three elements of which any four points do not form a nonsingular parallelogram.

An important property of a scale-free network which allows one to communicate between its nodes is the connectivity. From the simulation results it is known that such networks are resistant to random damage. It is also known from experiments that usually disconnecting such a graph is obtained by isolating a vertex. In this paper, we deal with a problem of isolating a vertex both experimentally and theoretically. For the theoretical results, we use the LCD model defined by Bollobas and Riordan. Among others, we prove that even after random deleting of nα vertices (mα edges) for α < (d − 1)/d, where d is the out-degree, with high probability, there are no isolated vertices in the remaining graph.

In this paper, we discuss the algebraic independence and algebraic relations, first, for reciprocal sums of even terms in Fibonacci numbers \( \sum\limits_{n = 1}^\infty {F_{2n}^{ - 2s}} \), and second, for sums of evenly even and unevenly even types \( \sum\limits_{n = 1}^\infty {F_{4n}^{ - 2s}}, \sum\limits_{n = 1}^\infty {F_{4n - 2}^{ - 2s}} \). The numbers \( \sum\limits_{n = 1}^\infty {F_{4n - 2}^{ - 2s}}, \sum\limits_{n = 1}^\infty {F_{4n - 2}^{ - 4}} \), and are shown to be algebraically independent, and each sum \( \sum\limits_{n = 1}^\infty {F_{4n - 2}^{ - 2s}} \left( {s \geqslant 4} \right) \) is written as an explicit rational function of these three numbers over \( \mathbb{Q} \). Similar results are obtained for various series of even type, including the reciprocal sums of Lucas numbers \( \sum\limits_{n = 1}^\infty {L_{2n}^{ - p}}, \sum\limits_{n = 1}^\infty {L_{4n}^{ - p}} \), and \( \sum\limits_{n = 1}^\infty {L_{4n - 2}^{ - p}} \).

This paper is concerned with the existence of badly approximable numbers in problems involving lacunary or sublacunary sequences. The principal results depend upon Peres–Schlag’s method.

In this work, recursive expansions in Hilbert space H = L 2[0, 1] are considered. We discuss a related notion of frames in finite-dimensional spaces. We also suggest a constructive approach to extend an arbitrary basis to obtain a tight frame. The algorithm of extending is applied to bases of a special form, whose Gram matrix is circulant. A construction of a chain of nested subspaces $$ \left\{ {{V^n}} \right\}_{n = 1}^\infty $$ is given, and in its foundation lies an example of a function that can be expressed as a linear combination of its contractions and translations. The main result of the paper is the theorem that provides the uniform convergence of recursive Fourier series with respect to the chain $$ \left\{ {{V^n}} \right\}_{n = 1}^\infty $$ for continuous functions.

Let A = D A + B be a block r × r, r ≥ 2, Hermitian matrix of order n, where D A is the block diagonal part of A. The main results of the paper are Theorems 2.1 and 2.2, which state the sharp inequalities $$ {\lambda_1}(A) \geqslant {\lambda_1}\left( {{D_A} + \xi B} \right)\,\,\,and\,\,\,{\lambda_n}(A) \leqslant {\lambda_n}\left( {{D_A} + \xi B} \right), - \frac{1}{{r - 1}} \leqslant \xi \leqslant 1, $$ and analyze the equality cases. Some implications of these results are indicated. As applications, matrices occurring in spectral graph theory are considered, and new lower bounds on the chromatic number of a graph are obtained. Bibliography: 7 titles.

We survey recent results concerning the combinatorial size of subsets of groups. For a cardinal κ, according to its arrangement in a group G, a subset of G is distinguished as κ-large, κ-small, κ-thin, κ-thick, and P κ -small. By analogy with topology, there arise the following combinatorial cardinal invariants of a group: density, cellularity, resolvability, spread, etc. The paper consists of 7 sections: Ballean context, Amenability, Ideals, Partitions, Packings, Around thin subsets, and Colorings.

This paper obtains an asymptotic formula for the number of solutions to the equation \( l_1^2 + { }l_2^2 + l_3^2 + l_4^2 = N \) in integers l1, l2, l3, l4 such that a < {ηlj} < b, where η is a quadratic irrational number, 0 ≤ a < b ≤ 1, j = 1, 2, 3, 4.

This paper concerns BMO-regularity and AK-stability for couples (X, Y) of quasi-Banach lattices of measurable functions on the measure space $ \left( {\mathbb{T},m} \right) \times \left( {\Omega, \mu } \right) $ , where $ \left( {\mathbb{T},m} \right) $ is the unit circle with Lebesgue measure. In an earlier work, S. Kislyakov introduced a weaker version of BMO-regularity and conjectured that this property is the same as the “strong” one in the case of couples of lattices having the Fatou property. Here we prove that these properties are indeed equivalent, thus verifying that BMO-regularity for couples is a self-dual property stable under division by a lattice. We also study another refinement of the AK-stability property and develop some techniques which allow us to slightly enlarge the class of weighted l p -valued lattices for which AK-stability implies BMO-regularity. Finally, we discuss some points which might be relevant to the yet unanswered question about the relationship between AK-stability and BMO-regularity in general. Bibliography: 15 titles.

When attacking Diophantine counting problems by the circle method, the use of smoothly weighted counting functions has become commonplace to avoid technical difficulties. It can, however, be problematic to then recover corresponding results for the unweighted number of solutions. This paper looks at quadratic forms in four or more variables representing an integer. We show how an asymptotic formula for the number of unweighted solutions in an expanding region can be obtained despite applying a weighted version of the circle method. Moreover, by carefully choosing the weight, the resulting error term is made nontrivial. Bibliography: 9 titles.

In this paper, we prove that every automorphism of a Chevalley group of type A l , D l , or E l , l ≥ 3, over a commutative local ring without 1/2 is standard, i.e., it is a composition of ring, inner, central, and graph automorphisms.

In this paper, we prove that the cardinality of the set of all precomplete classes for definite automata is continuum.

The completeness problem for bases of the form Φ ∪ ν, where Φ ⊆ Pk and ν is a finite system of automaton functions, is considered. Previously, the problem for k = 2 was solved by the author; it was also shown that there is an algorithm for determining the completeness of the system Φ∪ν when [Φ] = Pk. The paper is concerned with the case where [Φ] is the maximal (precomplete) class in Pk. The problem of completeness for systems Φ ∪ ν is shown to be undecidable if Φ is embedded in a Slupecki class and algorithmically decidable if Φ contains the class preserving all constants. Thus, the bases in Pk, k ≥ 3, can be classified according to their ability to guarantee the decidability of the completeness problem for automaton functions.

In this paper, we prove that every automorphism of an (elementary) Chevalley group of type A l , D l , or E l , l ≥ 2, over a commutative local ring with 1/2 is standard, i.e., is the composition of inner, ring, graph, and central automorphisms.

All groups considered in this paper will be finite. Our main result here is the following theorem. Let G be a solvable group in which the Sylow p-subgroups are either bicyclic or of order p3 for any p ∈ π(G). Then the derived length of G is at most 6. In particular, if G is an A4-free group, then the following statements are true: (1) G is a dispersive group; (2) if no prime q ∈ π(G) divides p2 + p + 1 for any prime p ∈ π(G), then G is Ore dispersive; (3) the derived length of G is at most 4.

In this work, we investigate the partially ordered monoids S over which the class of free (over a poset) S-posets is axiomatizable. Similar questions for S-sets were considered in papers of V. Gould, S. Bulman-Fleming, and A. A. Stepanova.

In this paper, we present a survey of results on automorphisms of distance-regular graphs obtained at the department of algebra and topology of IMM UB RAS in the last five years. Also, we explain the Higman method of application of the character theory to the investigation of automorphisms of distance-regular graphs.

Let B(m, n) be a free periodic group of arbitrary rank m with period n. In this paper, we prove that for all odd numbers n ≥ 1003 the normalizer of any nontrivial subgroup N of the group B(m, n) coincides with N if the subgroup N is free in the variety of all n-periodic groups. From this, there follows a positive answer for all prime numbers n > 997 to the following problem set by S. I. Adian in the Kourovka Notebook: is it true that none of the proper normal subgroups of the group B(m, n) of prime period n > 665 is a free periodic group? The obtained result also strengthens a similar result of A. Yu. Ol’shanskii by reducing the boundary of exponent n from n > 1078 to n ≥ 1003. For primes 665 < n ≤ 997, the mentioned question is still open.

The paper states and studies a problem that is closely related to the problems mentioned in the title.