Some results on embeddings of algebras, after de Bruijn and McKenzie

In 1957, N.G. de Bruijn showed that the symmetric group Sym(Ω) on an infinite set Ω contains a free subgroup on 2^card(Ω) generators, and proved a more general statement, a sample consequence of which is that for any group A of cardinality card(Ω), the group Sym(Ω) contains a coproduct of 2^card(Ω) copies of A, not only in the variety of all groups, but in any variety of groups to which A belongs. His key lemma is here generalized to an arbitrary variety of algebras V, and formulated as a statement about functors Set V. From this one easily obtains analogs of the results stated above with “group” and Sym(Ω) replaced by “monoid” and the monoid Self(Ω) of endomaps of Ω, by “associative K-algebra” and the K-algebra End_K (V) of endomorphisms of a K-vector-space V with basis Ω, and by “lattice” and the lattice Equiv(Ω) of equivalence relations on Ω. It is also shown, extending another result from de Bruijn's 1957 paper, that each of Sym(Ω), Self(Ω) and End_K(V) contains a coproduct of 2^card(Ω) copies of itself.That paper also gave an example of a group of cardinality 2^card(Ω) that was not embeddable in Sym(Ω), and R. McKenzie subsequently established a large class of such examples. Those results are shown here to be instances of a general property of the lattice of solution sets in Sym(Ω) of sets of equations with constants in Sym(Ω). Again, similar results - this time of varying strengths - are obtained for Self(Ω), End_K(V), and Equiv(Ω), and also for the monoid Rel(Ω) of binary relations on Ω.Many open questions and areas for further investigation are noted.     

Algebra Forms with $$d^{N} = 0$$ on Quantum Plane. Generalized Clifford Algebra Approach

We construct a q-analog of exterior calculus with a differential d satisfying d ^N = 0, where N ≥ 2 and q is a primitive Nth root of unity, on a noncommutative space and introduce a notion of a q-differential k-form. A noncommutative space we consider is a reduced quantum plane. Our construction of a q-analog of exterior calculus is based on a generalized Clifford algebra with four generators and on a graded q-differential algebra. We study the structure of the algebra of q-differential forms on a reduced quantum plane and show that the first order calculus induced by the differential d is a coordinate calculus. The explicit formulae for partial derivatives of this first order calculus are found.     

Some generalizations of the concept of a p-space

In this article, some generalizations of the concept of a p-space are introduced and studied. The notion of a source of a space in a larger space and the concepts of partial plumage, s-embedding, p-embedding, p^?-embedding, s-space, and p^?-space are defined and studied in depth (see Theorems 2.6, 2.7, 3.2, 4.3, 4.4, 4.10 and their corollaries). An example of a hereditarily p^?-space which is not a p-space and is a perfect image of a hereditarily p-space is indicated (Example 2.9). Among the main results, we establish that if a paracompact space X is p-embedded in a pseudocompact space as a dense subspace, then X is a p-space (Corollary 4.8), and that if X has a countable network and is p^?-embedded in a pseudocompact space, then X is metrizable (Corollary 4.11). The following problem is posed: is every paracompact Gδ-subspace of a pseudocompact space ?ech-complete?     

The geometry of k-transvection groups

Let k be a (commutative) field and G a group, then a conjugacy class of Abelian subgroups of G is called a class of k-transvection subgroups in G if and only if it generates G and any two elements of the class either commute or are full unipotent subgroups of the group they generate and which is isomorphic to (P)SL₂(k).In this paper we study the geometry of k-transvection groups. Given a class of k-transvection groups Σ, we consider a partial linear space whose points are the elements of Σ, and whose lines correspond to the groups generated by two noncommuting elements from Σ. We derive several properties of this partial linear space. These properties are used to give a characterization of the geometries of k-transvection groups and provide a classification of groups generated by k-transvection subgroups.     

The Bloch Approximation in Periodically Perforated Media

We consider a periodically heterogeneous and perforated medium filling an open domain Ω of ℝ^N. Assuming that the size of the periodicity of the structure and of the holes is O(ε), we study the asymptotic behavior, as ε → 0, of the solution of an elliptic boundary value problem with strongly oscillating coefficients posed in Ω^ε (Ω^ε being Ω minus the holes) with a Neumann condition on the boundary of the holes. We use Bloch wave decomposition to introduce an approximation of the solution in the energy norm which can be computed from the homogenized solution and the first Bloch eigenfunction. We first consider the case where Ωis ℝ^N and then localize the problem for a bounded domain Ω, considering a homogeneous Dirichlet condition on the boundary of Ω.     

Bass-Tits minimization of automata, quotients of trees and diameters

Let X be a tree and let G=Aut(X), Bass and Tits have given an algorithm to construct the ‘ultimate quotient’ of X by G starting with any quotient of X, an ‘edge-indexed’ graph. Using a sequence of integers that we compute at consecutive steps of the Bass-Tits (BT) algorithm, we give a lower bound on the diameter of the ultimate quotient of a tree by its automorphism group. For a tree X with finite quotient, this gives a lower bound on the minimum number of generators of a uniform X-lattice whose quotient graph coincides with G?X. This also gives a criterion to determine if the ultimate quotient of a tree is infinite. We construct an edge-indexed graph (A,i) for a deterministic finite state automaton and show that the BT algorithm for computing the ultimate quotient of (A,i) coincides with state minimizing algorithm for finite state automata. We obtain a lower bound on the minimum number of states of the minimized automaton. This gives a new proof that language for the word problem in a finitely generated group is regular if and only if the group is finite, and a new proof that the language of the membership problem for a subgroup is regular if and only if the subgroup has finite index.     

Exhausters af a positively homogeneous function *

Notions of upper exhauster and lower exhauster of a positively homogeneous (of the first degree) function h: ? ⁿ →? are introduced. They are linked to exhaustive families of upper convex and lower concave approximations of the function h. The pair of an upper exhauster and a lower exhauster is called a biexhauster of h. A calculus for biexhausters is described (in particular, a composition theorem is formulated). The problem of minimality of exhausters is stated. Necessary and sufficient conditions for a constrained minimum and a constrained maximum of a directionally differentiable function f: ? ⁿ →? are formulated in terms of exhausters of the directional derivative of f. In general, they are described by means of exhausters of the Hadamard upper and lower directional derivatives of the function f. To formulate conditions for a minimum, an upper exhauster is employed while conditions for a maximum are formulated via a lower exhauster of the respective directional derivative (the Hadamard lower derivative for a minimum and the Hadamard upper derivative for a maximum).

If a point x _o is not stationary then directions of steepest ascent and descent can also be calculated by means of exhausters.     

New parameters of subsets in polynomial association schemes

We define new parameters, a zero interval and a dual zero interval, of subsets in P- or Q-polynomial association schemes. A zero interval of a subset in a P-polynomial association scheme is a successive interval index for which the inner distribution vanishes, and a dual zero interval of a subset in a Q-polynomial association scheme is a successive interval index for which the dual inner distribution vanishes. We derive bounds of the lengths of a zero interval and a dual zero interval using the degree and dual degree respectively, and show that a subset in a P-polynomial association scheme (resp. a Q-polynomial association scheme) having a large length of a zero interval (resp. a dual zero interval) induces a completely regular code (resp. a Q-polynomial association scheme). Moreover, we consider the spherical analogue of a dual zero interval.     

Towards variational analysis in metric spaces: metric regularity and fixed points

The main results of the paper include (a) a theorem containing estimates for the surjection modulus of a “partial composition” of set-valued mappings between metric spaces which contains as a particlar case well-known Milyutin’s theorem about additive perturbation of a mapping into a Banach space by a Lipschitz mapping; (b) a “double fixed point” theorem for a couple of mappings, one from X into Y and another from Y to X which implies a fairly general version of the set-valued contraction mapping principle and also a certain (different) version of the first theorem.     

Bounds on the number of switchings for trajectories of piecewise analytic vector fields

We study the trajectories of systems $\text{x}\text{?}\text{= X(x)}$, where X is a continuous “extendably piecewise analytic” vector field, i.e., a continuous vector field X such that the domain of ? admits a locally finite partition $\text{I}$ into sets such that for each A ∈ $\text{I}$ there is a vector field X_A which is analytic on a neighborhood of the closure of A and whose restriction to A coincides with that of X. We prove that the trajectories are piecewise analytic, with a priori bounds on the number of switchings for all trajectories that stay in a fixed compact set and whose duration does not exceed a fixed number T. This result implies the existence of a regular synthesis for optimal control problems with a strictly convex Lagrangian, and a linear dynamics with polyhedral constraints on the controls.     

Geometry of 2 × 2 hermitian matrices

LetD be a division ring which possesses an involution a → α . Assume that is a proper subfield ofD and is contained in the center ofD. It is pointed out that ifD is of characteristic not two, D is either a separable quadratic extension of F or a division ring of generalized quaternions over F and that if D is of characteristic two,D is a separable quadratic extension ofF. Thus the trace map Tr:D → F, a → a + a is always surjective, which is formerly posed as an assumption in the fundamental theorem of n×n hermitian matrices overD when n ≥ 3 and now can be deleted. WhenD is a field, the fundamental theorem of 2 × 2 hermitian matrices overD has already been proved. This paper proves the fundamental theorem of 2×2 hermitian matrices over any division ring of generalized quaternions of characteristic not two This research was completed during a visit to the Academy of Mathematics and System Sciences, Chinese Academy of Sciences.     

A just basis

An old problem of P. Erdös and P. Turán asks whether there is a basisA of order 2 for which the number of representationsn=a+a′, a,a′∈A is bounded. Erd?s conjectured that such a basis does not exist. We answer a related finite problem and find a basis for which the number of representations is bounded in the square mean. Writing σ (n)=|{(a, a ^t ) ∈A ²:a+a′=n}| we prove that there exists a setA of nonnegative integers that forms a basis of order 2 (that is,s(n)≥1 for alln), and satisfies ∑_{n ? N} σ(N)² = O(N).     

Partially ordered knapsack and applications to scheduling

In the partially ordered knapsack problem (POK) we are given a set N of items and a partial order ?_P on N. Each item has a size and an associated weight. The objective is to pack a set N^′⊆N of maximum weight in a knapsack of bounded size. N^′ should be precedence-closed, i.e., be a valid prefix of ?_P. POK is a natural generalization, for which very little is known, of the classical Knapsack problem. In this paper we present both positive and negative results. We give an FPTAS for the important case of a two-dimensional partial order, a class of partial orders which is a substantial generalization of the series-parallel class, and we identify the first non-trivial special case for which a polynomial-time algorithm exists. Our results have implications for approximation algorithms for scheduling precedence-constrained jobs on a single machine to minimize the sum of weighted completion times, a problem closely related to POK.     

Some properties of c-covers of a pair of Lie algebras

In [H. Safa and H. Arabyani, On c-nilpotent multiplier and c-covers of a pair of Lie algebras, Commun. Algebra 45(10) (2017), 4429–4434], we characterized the structure of the c-nilpotent multiplier of a pair of Lie algebras in terms of its c-covering pairs and discussed some results on the existence of c-covers of a pair of Lie algebras. In the present paper, it is shown under some conditions that a relative c-central extension of a pair of Lie algebras is a homomorphic image of a c-covering pair. Moreover, we prove that a c-cover of a pair of finite dimensional Lie algebras, under some assumptions, has a unique domain up to isomorphism and also that every perfect pair of Lie algebras admits at least one c-cover. Finally, we discuss a result concerning the isoclinism of c-covering pairs.     

Remainders in compactifications of topological groups

In this paper, we consider the following question: when does a topological group G have a Hausdorff compactification bG with a remainder belonging to a given class of spaces? We extend the results of A.V. Arhangel'skii by showing that if a remainder of a non-locally compact topological group G has a countable open point-network or a locally Gδ-diagonal, then G and the compactification bG of G are separable and metrizable.     

Two-worker blocking congestion model with walk speed m in a no-passing circular passage system

This paper introduces a blocking model and closed-form expression of two workers traveling with walk speed m (m = integer) in a no-passing circular-passage system of n stations and assuming n = m + 2, 2m + 2, …. We develop a Discrete-Timed Markov Chain (DTMC) model to capture the workers’ changes of walk, pick, and blocked states, and quantify the throughput loss from blocking congestion by deriving a steady state probability in a closed-form expression. We validate the model with a simulation study. Additional simulation comparisons show that the proposed throughput model gives a good approximation of a general-sized system of n stations (i.e., n > 2), a practical walk speed system of real number m (i.e., m ? 1), and a bucket brigade order picking application.     

The spanning trees forced by the path and the star

A set S of trees of order n forces a tree T if every graph having each tree in S as a spanning tree must also have T as a spanning tree. A spanning tree forcing set for order n that forces every tree of order n. A spanning-tree forcing set S is a test set for panarboreal graphs, since a graph of order n is panarboreal if and only if it has all of the trees in S as spanning trees. For each positive integer n ≠ 1, the star belongs to every spanning tree forcing set for order n. The main results of this paper are a proof that the path belongs to every spanning-tree forcing set for each order n ∉ {1, 6, 7, 8} and a computationally tractable characterization of the trees of order n ≥ 15 forced by the path and the star. Corollaries of those results include a construction of many trees that do not belong to any minimal spanning tree forcing set for orders n ≥ 15 and a proof that the following related decision problem is NP-complete: an instance is a pair (G, T) consisting of a graph G of order n and maximum degree n - 1 with a hamiltonian path, and a tree T of order n; the problem is to determine whether T is a spanning tree of G. © 1996 John Wiley & Sons, Inc.     

On the structure of a semigroup of operators with finite-dimensional ranges

In the present paper, we describe the structure of a strongly continuous operator semigroup T(t) (where T: ?₊ → End X and X is a complex Banach space) for which ImT(t) is a finite-dimensional space for all t > 0. It is proved that such a semigroup is always the direct sum of a zero semigroup and a semigroup acting in a finite-dimensional space. As examples of applications, we discuss differential equations containing linear relations, orbits of a special form, and the possibility of embedding an operator in a C ₀-semigroup.     

Subdivision Extendibility

Let H be a multigraph and G a graph containing a subgraph isomorphic to a subdivision of H, with S ⊂ V(G) (the ground set) the image of V(H) under the isomorphism. We consider connectivity and minimum degree or degree sum conditions sufficient to imply there is a spanning subgraph of G isomorphic to a subdivision of H on the same ground set S. These results generalize a number of theorems in the literature.