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.     

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.     

Tambarization of a Mackey functor and its application to the Witt–Burnside construction

For an arbitrary group G, a (semi-)Mackey functor is a pair of covariant and contravariant functors from the category of G-sets, and is regarded as a G-bivariant analog of a commutative (semi-)group. In this view, a G-bivariant analog of a (semi-)ring should be a (semi-)Tambara functor. A Tambara functor is firstly defined by Tambara, which he called a TNR-functor, when G is finite. As shown by Brun, a Tambara functor plays a natural role in the Witt–Burnside construction.It will be a natural question if there exist sufficiently many examples of Tambara functors, compared to the wide range of Mackey functors. In the first part of this article, we give a general construction of a Tambara functor from any Mackey functor, on an arbitrary group G. In fact, we construct a functor from the category of semi-Mackey functors to the category of Tambara functors. This functor gives a left adjoint to the forgetful functor, and can be regarded as a G-bivariant analog of the monoid-ring functor.In the latter part, when G is finite, we investigate relations with other Mackey-functorial constructions — crossed Burnside ring, Elliott?s ring of G-strings, Jacobson?s F-Burnside ring — all these lead to the study of the Witt–Burnside construction.     

Topological vector spaces, compacta, and unions of subspaces

In the first two sections, we study when a σ-compact space can be covered by a point-finite family of compacta. The main result in this direction concerns topological vector spaces. Theorem 2.4 implies that if such a space L admits a countable point-finite cover by compacta, then L has a countable network. It follows that if f is a continuous mapping of a σ-compact locally compact space X onto a topological vector space L, and fibers of f are compact, then L is a σ-compact space with a countable network (Theorem 2.10). Therefore, certain σ-compact topological vector spaces do not have a stronger σ-compact locally compact topology.In the last, third section, we establish a result going in the orthogonal direction: if a compact Hausdorff space X is the union of two subspaces which are homeomorphic to topological vector spaces, then X is metrizable (Corollary 3.2).     

Zeta Functions for Curves and Log Canonical Models

The topological zeta function and Igusa's local zeta functionare respectively a geometrical invariant associated to a complexpolynomial f and an arithmetical invariant associated to a polynomialf over a p-adic field. When f is a polynomial in two variables we prove a formula forboth zeta functions in terms of the so-called log canonicalmodel of f^-1{0} in A². This result yields moreover a conceptualexplanation for a known cancellation property of candidate polesfor these zeta functions. Also in the formula for Igusa's localzeta function appears a remarkable non-symmetric ‘q-deformation’of the intersection matrix of the minimal resolution of a Hirzebruch-Jungsingularity. 1991 Mathematics Subject Classification: 32S5011S80 14E30 (14G20)     

On the lattice formed by all normal subloops of a finite loop

All normal subloops of a loopG form a modular latticeL _n (G). It is shown that a finite loopG has a complemented normal subloop lattice if and only ifG is a direct product of simple subloops. In particular,L _n (G) is a Boolean algebra if and only if no two isomorphic factors occurring in a decomposition ofG are abelian groups. The normal subloop lattice of a finite loop is a projective geometry if and only ifG is an elementary abelianp-group for some primep.     

A new algorithm for minimizing convex functions over convex sets

Let be a convex set for which there is an oracle with the following property. Given any pointz∈ℝ ⁿ the oracle returns a “Yes” ifz∈S; whereas ifz∉S then the oracle returns a “No” together with a hyperplane that separatesz fromS. The feasibility problem is the problem of finding a point inS; the convex optimization problem is the problem of minimizing a convex function overS. We present a new algorithm for the feasibility problem. The notion of a volumetric center of a polytope and a related ellipsoid of maximum volume inscribable in the polytope are central to the algorithm. Our algorithm has a significantly better global convergence rate and time complexity than the ellipsoid algorithm. The algorithm for the feasibility problem easily adapts to the convex optimization problem.     

Total Colorings Of Degenerate Graphs

A total coloring of a graph G is a coloring of all elements of G, i.e. vertices and edges, such that no two adjacent or incident elements receive the same color. A graph G is s-degenerate for a positive integer s if G can be reduced to a trivial graph by successive removal of vertices with degree ≤s. We prove that an s-degenerate graph G has a total coloring with Δ+1 colors if the maximum degree Δ of G is sufficiently large, say Δ≥4s+3. Our proof yields an efficient algorithm to find such a total coloring. We also give a lineartime algorithm to find a total coloring of a graph G with the minimum number of colors if G is a partial k-tree, that is, the tree-width of G is bounded by a fixed integer k.     

𝔏-Rickart Modules

It is well known that the Rickart property of rings is not a left-right symmetric property. We extend the notion of the left Rickart property of rings to a general module theoretic setting and define 𝔏-Rickart modules. We study this notion for a right R-module M _R where R is any ring and obtain its basic properties. While it is known that the endomorphism ring of a Rickart module is a right Rickart ring, we show that the endomorphism ring of an 𝔏-Rickart module is not a left Rickart ring in general. If M _R is a finitely generated 𝔏-Rickart module, we prove that End _R (M) is a left Rickart ring. We prove that an 𝔏-Rickart module with no set of infinitely many nonzero orthogonal idempotents in its endomorphism ring is a Baer module. 𝔏-Rickart modules are shown to satisfy a certain kind of nonsingularity which we term “endo-nonsingularity.” Among other results, we prove that M is endo-nonsingular and End _R (M) is a left extending ring iff M is a Baer module and End _R (M) is left cononsingular.     

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 Ω.     

Path coupling without contraction

Path coupling is a useful technique for simplifying the analysis of a coupling of a Markov chain. Rather than defining and analysing the coupling on every pair in Ω×Ω, where Ω is the state space of the Markov chain, analysis is done on a smaller set SΩ×Ω. If the coefficient of contraction β is strictly less than one, no further analysis is needed in order to show rapid mixing. However, if β=1 then analysis (of the variance) is still required for all pairs in Ω×Ω. In this paper we present a new approach which shows rapid mixing in the case β=1 with a further condition which only needs to be checked for pairs in S, greatly simplifying the work involved. We also present a technique applicable when β=1 and our condition is not met.     

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 interval function of a connected graph and road systems

Let V be a finite nonempty set. In this paper, a road system on V (as a generalization of the set of all geodesics in a connected graph G with V(G)=V) and an intervaloid function on V (as a generalization of the interval function (in the sense of Mulder) of a connected graph G with V(G)=V) are introduced. A natural bijection of the set of all intervaloid functions on V onto the set of all road systems on V is constructed. This bijection enables to deduce an axiomatic characterization of the interval function of a connected graph G from a characterization of the set of all geodesics in G.     

On the generation of bicliques of a graph

An independent set of a graph is a subset of pairwise non-adjacent vertices. A complete bipartite set B is a subset of vertices admitting a bipartition B=X∪Y, such that both X and Y are independent sets, and all vertices of X are adjacent to those of Y. If both X,Y≠∅, then B is called proper. A biclique is a maximal proper complete bipartite set of a graph. When the requirement that X and Y are independent sets of G is dropped, we have a non-induced biclique. We show that it is NP-complete to test whether a subset of the vertices of a graph is part of a biclique. We propose an algorithm that generates all non-induced bicliques of a graph. In addition, we propose specialized efficient algorithms for generating the bicliques of special classes of graphs.     

Nonhomogeneous Neumann problem for the Poisson equation in domains with an external cusp

In this work we analyze the existence and regularity of the solution of a nonhomogeneous Neumann problem for the Poisson equation in a plane domain Ω with an external cusp. In order to prove that there exists a unique solution in H¹(Ω) using the Lax–Milgram theorem we need to apply a trace theorem. Since Ω is not a Lipschitz domain, the standard trace theorem for H¹(Ω) does not apply, in fact the restriction of H¹(Ω) functions is not necessarily in L²(∂Ω). So, we introduce a trace theorem by using weighted Sobolev norms in Ω. Under appropriate assumptions we prove that the solution of our problem is in H²(Ω) and we obtain an a priori estimate for the second derivatives of the solution.     

A note on the computational complexity of graph vertex partition

A stable set of a graph is a vertex set in which any two vertices are not adjacent. It was proven in [A. Brandstädt, V.B. Le, T. Szymczak, The complexity of some problems related to graph 3-colorability, Discrete Appl. Math. 89 (1998) 59-73] that the following problem is NP-complete: Given a bipartite graph G, check whether G has a stable set S such thatG-Sis a tree. In this paper we prove the following problem is polynomially solvable: Given a graph G with maximum degree 3 and containing no vertices of degree 2, check whether G has a stable set S such thatG-Sis a tree. Thus we partly answer a question posed by the authors in the above paper. Moreover, we give some structural characterizations for a graph G with maximum degree 3 that has a stable set S such that G-S is a tree.     

Mean field limits for nonlinear spatially extended Hawkes processes with exponential memory kernels

We consider spatially extended systems of interacting nonlinear Hawkes processes modeling large systems of neurons placed in ${\mathbb{R}}^d$ and study the associated mean field limits. As the total number of neurons tends to infinity, we prove that the evolution of a typical neuron, attached to a given spatial position, can be described by a nonlinear limit differential equation driven by a Poisson random measure. The limit process is described by a neural field equation. As a consequence, we provide a rigorous derivation of the neural field equation based on a thorough mean field analysis.     

Approximation algorithms for constructing some required structures in digraphs

We consider a new problem of constructing some required structures in digraphs, where all arcs installed in such required structures are supposed to be cut from some pieces of a specific material of length L. Formally, we consider the model: a digraph D = (V, A; w), a structure S and a specific material of length L, where w: A → R⁺, we are asked to construct a subdigraph D′ from D, having the structure S, such that each arc in D′ is constructed by a part of a piece or/and some whole pieces of such a specific material, the objective is to minimize the number of pieces of such a specific material to construct all arcs in D′.     

Full Ideals

Contractedness of 𝔪-primary integrally closed ideals played a central role in the development of Zariski's theory of integrally closed ideals in two-dimensional regular local rings (R, 𝔪). In such rings, the contracted 𝔪-primary ideals are known to be characterized by the property that I: 𝔪 = I: x for some x ∈ 𝔪 ?𝔪². We call the ideals with this property full ideals and compare this class of ideals with the classes of 𝔪-full ideals, basically full ideals, and contracted ideals in higher dimensional regular local rings. The 𝔪-full ideals are easily seen to be full. In this article, we find a sufficient condition for a full ideal to be 𝔪-full. We also show the equivalence of the properties full, 𝔪-full, contracted, integrally closed, and normal, for the class of parameter ideals. We then find a sufficient condition for a basically full parameter ideal to be full.     

The Galois Theory of Matrix C-rings

A theory of monoids in the category of bicomodules of a coalgebra C or C-rings is developed. This can be viewed as a dual version of the coring theory. The notion of a matrix ring context consisting of two bicomodules and two maps is introduced and the corresponding example of a C-ring (termed a matrix C -ring) is constructed. It is shown that a matrix ring context can be associated to any bicomodule which is a one-sided quasi-finite injector. Based on this, the notion of a Galois module is introduced and the structure theorem, generalising Schneider’s Theorem II [Schneider, Isr. J. Math., 72:167–195, 1990], is proven. This is then applied to the C-ring associated to a weak entwining structure and a structure theorem for a weak A-Galois coextension is derived. The theory of matrix ring contexts for a firm coalgebra (or infinite matrix ring contexts) is outlined. A Galois connection associated to a matrix C-ring is constructed. Dedicated to Stef Caenepeel on the occasion of his 50th birthday.