Edge colorings of graphs embeddable in a surface of low genus

In this paper, by using the Discharging Method, we show that any graph with maximum degree Δ 8 that is embeddable in a surface Σ of characteristic χ(Σ) 0 is class one and any graph with maximum degree Δ 9 that is embeddable in a surface Σ of characteristic χ(Σ) = − 1 is class one. For surfaces of characteristic 0 or −1, these results improve earlier results of Mel'nikov.     

Regularity and convergence of stochastic convolutions in duals of nuclear Fréchet spaces

Let Φ′ be the strong dual of a nuclear Fréchet space Φ. In this paper we present regularity properties, weak convergence, and convergence in probability and in mean square of Φ′-valued stochastic evolution equations and convolutions with respect to Φ′-valued cadlag martingales.     

Some Infinite Families of Locally Partial Geometries Generalizing the Classical Laguerre Planes

Starting with a subgeometry Ω embedded in a β-dimensional projective space PG(β, q), β 1, we construct inductively a series of rank n residually connected geometries Γ^{(n, β, Ω)}, n β, by putting Γ^{(β, β, Ω)} = Ω and extending Γ^{(n - 1, β, Ω)} with a partial geometry.     

The rate of convergence for the cyclic projections algorithm III: Regularity of convex sets

The cyclic projections algorithm is an important method for determining a point in the intersection of a finite number of closed convex sets in a Hilbert space. That is, for determining a solution to the “convex feasibility” problem. This is the third paper in a series on a study of the rate of convergence for the cyclic projections algorithm. In the first of these papers, we showed that the rate could be described in terms of the “angles” between the convex sets involved. In the second, we showed that these angles often had a more tractable formulation in terms of the “norm” of the product of the (nonlinear) metric projections onto related convex sets.In this paper, we show that the rate of convergence of the cyclic projections algorithm is also intimately related to the “linear regularity property” of Bauschke and Borwein, the “normal property” of Jameson (as well as Bakan, Deutsch, and Li’s generalization of Jameson’s normal property), the “strong conical hull intersection property” of Deutsch, Li, and Ward, and the rate of convergence of iterated parallel projections. Such properties have already been shown to be important in various other contexts as well.     

Finding the exact bound of the maximum degrees of class two graphs embeddable in a surface of characteristic

In this paper, we consider the problem of determining the maximum of the set of maximum degrees of class two graphs that can be embedded in a surface. For each surface Σ, we define Δ(Σ)=max{Δ(G)| G is a class two graph of maximum degree Δ that can be embedded in Σ}. Hence Vizing's Planar Graph Conjecture can be restated as Δ(Σ)=5 if Σ is a plane. We show that Δ(Σ)=7 if (Σ)=−1 and Δ(Σ)=8 if (Σ){−2,−3}.     

Interpolation of characteristic classes of singular hypersurfaces

We show that the Chern–Schwartz–MacPherson class of a hypersurface X in a nonsingular variety M ‘interpolates’ between two other notions of characteristic classes for singular varieties, provided that the singular locus of X is smooth and that certain numerical invariants of X are constant along this locus. This allows us to define a lift of the Chern–Schwartz–MacPherson class of such ‘nice’ hypersurfaces to intersection homology. As another application, the interpolation result leads to an explicit formula for the Chern–Schwartz–MacPherson class of X in terms of its polar classes.     

Restrictions of Symmetric Invariants of a Complex Semisimple Lie Algebra and Some Applications

Let 𝔤 be a finite-dimensional complex semisimple Lie algebra and σ an arbitrary semisimple automorphism of 𝔤. Let 𝔱 be a Cartan subalgebra of 𝔨 = 𝔤^σ and 𝔥 =Z _𝔤(𝔱) be the centralizer of 𝔱 in 𝔤. Then 𝔥 is a σ-invariant Cartan subalgebra of 𝔤 and 𝔱 = 𝔥^σ. Let W(𝔤, 𝔥) be the Weyl group. One knows that Δ(𝔤, 𝔱), the set of roots of 𝔤 in 𝔱, is also a root system. It is proved that the corresponding Weyl group W(𝔤, 𝔱) is isomorphic to W(𝔤, 𝔥)^σ, which is the subgroup of W(𝔤, 𝔥) consisting of those elements commuting with σ. It is also shown that the image of the restriction map S(𝔥*) ^{W(𝔤, 𝔥)} → S(𝔱*) ^{W(𝔨, 𝔱)}, where S(𝔥*) and S(𝔱*) are the polynomial algebras on 𝔥 and 𝔱, respectively, is exactly S(𝔱*) ^{W(𝔤, 𝔱)}. Based on the above result, we also get a complete classification of the pairs (𝔤, σ) such that 𝔤^σ is noncohomologous to zero in 𝔤.     

Existence of three solutions for a class of elliptic eigenvalue problems

In this paper, we consider a problem of the type −Δu = λ(f(u) + μg(u)) in Ω, u¦∂Ω = 0, where Ω Rⁿ is an open-bounded set, f, g are continuous real functions on R, and λ, μ ε R. As an application of a new approach to nonlinear eigenvalues problems, we prove that, under suitable hypotheses, if ¦μ¦ is small enough, then there is some λ > 0 such that the above problem has at least three distinct weak solutions in W₀^1,2(Ω).     

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.     

A general framework of compactly supported splines and wavelets

Let {V_k} be a nested sequence of closed subspaces that constitute a multiresolution analysis of L²( ). We characterize the family Φ = {φ} where each φ generates this multiresolution analysis such that the two-scale relation of φ is governed by a finite sequence. In particular, we identify the ε Φ that has minimum support. We also characterize the collection Ψ of functions η such that each η generates the orthogonal complementary subspaces W_k of V_k, . In particular, the minimally supported ψ ε Ψ is determined. Hence, the “B-spline” and “B-wavelet” pair (, ψ) provides the most economical and computational efficient “spline” representations and “wavelet” decompositions of L² functions from the “spline” spaces V_k and “wavelet” spaces W_k, k . A very general duality principle, which yields the dual bases of both {(·−j):j and {η(·−j):j } for any η ε Ψ by essentially interchanging the pair of two-scale sequences with the pair of decomposition sequences, is also established. For many filtering applications, it is very important to select a multiresolution for which both and ψ have linear phases. Hence, “non-symmetric” and ψ, such as the compactly supported orthogonal ones introduced by Daubechies, are sometimes undesirable for these applications. Conditions on linear-phase φ and ψ are established in this paper. In particular, even-order polynomial B-splines and B-wavelets φ_m and ψ_m have linear phases, but the odd-order B-wavelet only has generalized linear phases.     

Polynomial identity rings as rings of functions

We generalize the usual relationship between irreducible Zariski closed subsets of the affine space, their defining ideals, coordinate rings, and function fields, to a non-commutative setting, where “varieties” carry a PGL_n-action, regular and rational “functions” on them are matrix-valued, “coordinate rings” are prime polynomial identity algebras, and “function fields” are central simple algebras of degree n. In particular, a prime polynomial identity algebra of degree n is finitely generated if and only if it arises as the “coordinate ring” of a “variety” in this setting. For n=1 our definitions and results reduce to those of classical affine algebraic geometry.     

Borel ideals vs. Borel sets of countable relations and trees

For every μ < ω₁, let I_μ be the ideal of all sets S ω^μ whose order type is <ω^μ. If μ = 1, then I₁ is simply the ideal of all finite subsets of ω, which is known to be Σ⁰₂-complete. We show that for every μ < ω₁, I_μ is Σ⁰_2μ-complete. As corollaries to this theorem, we prove that the set WO_ωμ of well orderings Rω × ω of order type <ω^μ is Σ⁰_2μ-complete, the set LP_μ of linear orderings R ω × ω that have a μ-limit point is Σ⁰_2μ+1-complete. Similarly, we determine the exact complexity of the set LT_μ of trees T ^<ωω of Luzin height <μ, the set WR_μ of well-founded partial orderings of height <μ, the set LR_μ of partial orderings of Luzin height <μ, the set WF_μ of well-founded trees T ^<ωω of height <μ(the latter is an old theorem of Luzin). The proofs use the notions of Wadge reducibility and Wadge games. We also present a short proof to a theorem of Luzin and Garland about the relation between the height of ‘the shortest tree’ representing a Borel set and the complexity of the set.     

Forbidden Families of Geometric Permutations in ℝd

A geometric permutation induced by a transversal line of a finite family ℱ of disjoint convex sets in ℝ^d is the order in which the transversal meets the members of the family. We prove that for each natural k, each family of k permutations is realizable (as a family of geometric permutations of some ℱ) in ℝ^d for d ≥ 2k – 1, but there is a family of k permutations which is non-realizable in ℝ^d for d ≤ 2k – 2.     

Asymptotic distribution of the increase of the largest canonical correlation when one of the vectors is augmented

Let r₁ > r₂ > … be the sample canonical correlations in a sample of size n from a multivariate normal population partitioned into two subvectors with population canonical correlations ₁ > ₂ > …. Let one of the subvectors be augmented by adding one or more variables to it. For the increase in the largest canonical correlation, Δr in the sample and Δ in the population, it is shown that √n(Δr − Δ) → ^DN(0, σ²) and a formula for σ² is derived.     

Existence of maximal solutions

Let Ω be a plane bounded region. Let U = {U_μ(P):μ(P)εL∞(Ω), u_μ ε H²_{2, 0}(Ω) and a(P, μ(P))u_μ,xx + 2b(P, μ(P))u_μ,xy + c(P, μ(P))u_μ,vv = ƒ(P) for P ε Ω; here we are given a(P, X), b(P, X), c(P, X) ε L_∞(Ω × E¹), ƒ(P) ε L_p(Ω) with p > 2, and our partial differential equation is uniformly elliptic. The functions μ(P) are called profiles. We establish sufficient conditions—which when they apply are constructive—that there exist a μ₀ ε L_∞(Ω) such that u_μ0 (P) u_μ(P) for all P ε Ω and for each μ ε L_∞(Ω). Similar results are obtained for a difference equation and convergence is proved.