Separable algebras over infinite fields are 2-generated and finitely presented

We prove that every separable algebra over an infinite field F admits a presentation with 2 generators and finitely many relations. In particular, this is true for finite direct sums of matrix algebras over F and for group algebras FG, where G is a finite group such that the order of G is invertible in F. We illustrate the usefulness of such presentations by using them to find a polynomial criterion to decide when 2 ordered pairs of 2 × 2 matrices (A, B) and (A′, B′) with entries in a commutative ring R are automorphically conjugate over the matrix algebra M ₂(R), under an additional assumption that both pairs generate M ₂(R) as an R-algebra.     

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.     

Acyclic edge colorings of planar graphs and seriesparallel graphs

A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic edge chromatic number of G, denoted by a′(G), is the least number of colors in an acyclic edge coloring of G. Alon et al. conjectured that a′(G) ⩽ Δ(G) + 2 for any graphs. For planar graphs G with girth g(G), we prove that a′(G) ⩽ max{2Δ(G) − 2, Δ(G) + 22} if g(G) ⩾ 3, a′(G) ⩽ Δ(G) + 2 if g(G) ⩾ 5, a′(G) ⩽ Δ(G) + 1 if g(G) ⩾ 7, and a′(G) = Δ(G) if g(G) ⩾ 16 and Δ(G) ⩾ 3. For series-parallel graphs G, we have a′(G) ⩽ Δ(G) + 1. This work was supported by National Natural Science Foundation of China (Grant No. 10871119) and Natural Science Foundation of Shandong Province (Grant No. Y2008A20).     

Linear coloring of graphs embeddable in a surface of nonnegative characteristic

A proper vertex coloring of a graph G is linear if the graph induced by the vertices of any two color classes is the union of vertex-disjoint paths. The linear chromatic number lc(G) of the graph G is the smallest number of colors in a linear coloring of G. In this paper, we prove that every graph G with girth g(G) and maximum degree Δ(G) that can be embedded in a surface of nonnegative characteristic has lc(G) = Δ(2G )+ 1 if there is a pair (Δ, g) ∈ {(13, 7), (9, 8), (7, 9), (5, 10), (3, 13)} such that G s...     

Abelian group pairs having a trivial coGalois group

Torsion-free covers are considered for objects in the category q ₂. Objects in the category q ₂ are just maps in R-Mod. For R = ℤ, we find necessary and sufficient conditions for the coGalois group G(A → B), associated to a torsion-free cover, to be trivial for an object A → B in q ₂. Our results generalize those of E. Enochs and J. Rado for abelian groups.     

Injective (Δ + 1)-coloring of planar graphs with girth 6

A vertex coloring of a graph G is called injective if every two vertices joined by a path of length 2 get different colors. The minimum number χ _i (G) of the colors required for an injective coloring of a graph G is clearly not less than the maximum degree Δ(G) of G. There exist planar graphs with girth g ≥ 6 and χ _i = Δ+1 for any Δ ≥ 2. We prove that every planar graph with Δ ≥ 18 and g ≥ 6 has χ _i ≤ Δ + 1.     

On the description of overgroups of E(m,R)?E(n,R)

The subgroups E(m,R) ⊗ E(n,R) ≤ H ≤ G = GL(mn,R) are studied under the assumption that the ring R is commutative and m, n ≥ 3. The group GL _m ⊗GL _n is defined by equations, the normalizer of the group E(m,R) ⊗ E(n,R) is calculated, and with each intermediate subgroup H it is associated a uniquely determined lower level (A,B,C), where A,B,C are ideals in R such that mA,A ² ≤ B ≤ A and nA,A ² ≤ C ≤ A. The lower level specifies the largest elementary subgroup satisfying the condition E(m, n,R, A,B,C) ≤ H. The standard answer to this problem asserts that H is contained in the normalizer N _G (E(m,n,R, A,B,C)). Bibliography: 46 titles.     

Acyclic Edge Coloring of Planar Graphs Without Small Cycles

A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic edge chromatic number of G, denoted by a′(G), is the least number of colors in an acyclic edge coloring of G. Alon et al. conjectured that a′(G) ≤ Δ(G) + 2 for any graphs. In this paper, it is shown that the conjecture holds for planar graphs without 4- and 5-cycles or without 4- and 6-cycles.     

On constrained generalized inverses of matrices and their properties

A matrix G is called a generalized inverse (g-invserse) of matrix A if AGA = A and is denoted by G = A ⁻. Constrained g-inverses of A are defined through some matrix expressions like E(AE)⁻, (FA)⁻ F and E(FAE)⁻ F. In this paper, we derive a variety of properties of these constrained g-inverses by making use of the matrix rank method. As applications, we give some results on g-inverses of block matrices, and weighted least-squares estimators for the general linear model.     

On Compact Graphs

Let G be a finite simple graph with adjacency matrix A, and let P（A） be the convex closure of the set of all permutation matrices commuting with A. G is said to be compact if every doubly stochastic matrix which commutes with A is in P（A）. In this paper, we characterize 3-regular compact graphs and prove that if G is a connected regular compact graph, G - v is also compact, and give a family of almost regular compact connected graphs.     

When do random subsets decompose a finite group?

Let A, B be two random subsets of a finite group G. We consider the event that the products of elements from A and B span the whole group, i.e. [AB ∪ BA = G]. The study of this event gives rise to a group invariant we call Θ(G). Θ(G) is between 1/2 and 1, and is 1 if and only if the group is abelian. We show that a phase transition occurs as the size of A and B passes √Θ(G)|G| log |G|; i.e. for any ɛ > 0, if the size of A and B is less than (1 − ɛ)√Θ(G)|G| log |G|, then with high probability AB ∪ BA ≠ G. If A and B are larger than (1 + ɛ)√Θ(G)|G| log |G|, then AB ∪ BA = G with high probability.     

The Entire Coloring of Series-Parallel Graphs

The entire chromatic number X_(vef)(G) of a plane graph G is the minimal number of colors needed for coloring vertices, edges and faces of G such that no two adjacent or incident elements are of the same color. Let G be a series-parallel plane graph, that is, a plane graph which contains no subgraphs homeomorphic to K_(4-) It is proved in this paper that X_(vef)(G)≤max{8, △(G) 2} and X_(vef)(G)=△ 1 if G is 2-connected and △(G)≥6.     

Game-perfect graphs

A graph coloring game introduced by Bodlaender (Int J Found Comput Sci 2:133–147, 1991) as coloring construction game is the following. Two players, Alice and Bob, alternately color vertices of a given graph G with a color from a given color set C, so that adjacent vertices receive distinct colors. Alice has the first move. The game ends if no move is possible any more. Alice wins if every vertex of G is colored at the end, otherwise Bob wins. We consider two variants of Bodlaender’s graph coloring game: one (A) in which Alice has the right to have the first move and to miss a turn, the other (B) in which Bob has these rights. These games define the A-game chromatic number resp. the B-game chromatic number of a graph. For such a variant g, a graph G is g-perfect if, for every induced subgraph H of G, the clique number of H equals the g-game chromatic number of H. We determine those graphs for which the game chromatic numbers are 2 and prove that the triangle-free B-perfect graphs are exactly the forests of stars, and the triangle-free A-perfect graphs are exactly the graphs each component of which is a complete bipartite graph or a complete bipartite graph minus one edge or a singleton. From these results we may easily derive the set of triangle-free game-perfect graphs with respect to Bodlaender’s original game. We also determine the B-perfect graphs with clique number 3. As a general result we prove that complements of bipartite graphs are A-perfect.      

Acyclic total colorings of planar graphs without <Emphasis Type="Italic">l</Emphasis> cycles

A proper total coloring of a graph G such that there are at least 4 colors on those vertices and edges incident with a cycle of G, is called acyclic total coloring. The acyclic total chromatic number of G is the least number of colors in an acyclic total coloring of G. In this paper, it is proved that the acyclic total chromatic number of a planar graph G of maximum degree at least k and without l cycles is at most Δ(G) + 2 if (k, l) ∈ {(6, 3), (7, 4), (6, 5), (7, 6)}.     

Geometry of rectangular block triangular matrices

Let D be any division ring, and let T（mi,ni,k） be the set of k × k （k ≥ 2） rectangular block triangular matrices over D. For A, B ∈ T（mi,ni,k）, if rank（A - B） = 1, then A and B are said to be adjacent and denoted by A -B. A map T ： T（mi,ni,k） -〉 T（mi,ni,k） is said to be an adjacency preserving map in both directions if A - B if and only if φ（A） φ（B）. Let G be the transformation group of all adjacency preserving bijections in both directions on T（mi,ni,k）. When m1,nk ≥ 2, we characterize the algebraic structure of G, and obtain the fundamental theorem of rectangular block triangular matrices over D.     

Quadratically normal and congruence-normal matrices

A matrix A ∈ C ^n×n is unitarily quasidiagonalizable if A can be brought by a unitary similarity transformation to a block diagonal form with 1 × 1 and 2 × 2 diagonal blocks. In particular, the square roots of normal matrices, i.e., the so-called quadratically normal matrices are unitarily quasidiagonalizable. A matrix A ∈ C ^n×n is congruence-normal if B = A[`(A)] B = A\overline A is a conventional normal matrix. We show that every congruence-normal matrix A can be brought by a unitary congruence transformation to a block diagonal form with 1 × 1 and 2 × 2 diagonal blocks. Our proof emphasizes andexploitsalikenessbetween theequations X <sup>2</sup> = B and X[`(X)] = B X\overline X = B for a normal matrix B. Bibliography: 13 titles.     

Positivity and Convexity in Rings of Fractions

Given a commutative ring A equipped with a preordering A⁺ (in the most general sense, see below), we look for a fractional ring extension (= “ring of quotients” in the sense of Lambek et al. [L]) as big as possible such that A⁺ extends to a preordering R⁺ of R (i.e. with A ∩ R⁺ = A⁺) in a natural way. We then ask for subextensions A ⊂ B of A ⊂ R such that A is convex in B with respect to B⁺ : = B ∩ R⁺. Supported by DFG. A short form of this article has been delivered at the conference Carthapos 2006 at Carthago (Tunisia).     

Multigraphs with Δ ≥ 3 are Totally-(2Δ−1)-Choosable

The total graph T(G) of a multigraph G has as its vertices the set of edges and vertices of G and has an edge between two vertices if their corresponding elements are either adjacent or incident in G. We show that if G has maximum degree Δ(G), then T(G) is (2Δ(G) − 1)-choosable. We give a linear-time algorithm that produces such a coloring. The best previous general upper bound for Δ(G) > 3 was , by Borodin et al. When Δ(G) = 4, our algorithm gives a better upper bound. When Δ(G)∈{3,5,6}, our algorithm matches the best known bound. However, because our algorithm is significantly simpler, it runs in linear time (unlike the algorithm of Borodin et al.).     

Topological *-algebras withC*-enveloping algebras II

UniversalC*-algebrasC*(A) exist for certain topological *-algebras called algebras with aC*-enveloping algebra. A Frechet *-algebraA has aC*-enveloping algebra if and only if every operator representation ofA mapsA into bounded operators. This is proved by showing that every unbounded operator representation π, continuous in the uniform topology, of a topological *-algebraA, which is an inverse limit of Banach *-algebras, is a direct sum of bounded operator representations, thereby factoring through the enveloping pro-C*-algebraE(A) ofA. Given aC*-dynamical system (G,A,α), any topological *-algebraB containingC _c (G,A) as a dense *-subalgebra and contained in the crossed productC*-algebraC*(G,A,α) satisfiesE(B) =C*(G,A,α). IfG = ℝ, ifB is an α-invariant dense Frechet *-subalgebra ofA such thatE(B) =A, and if the action α onB ism-tempered, smooth and by continuous *-automorphisms: then the smooth Schwartz crossed productS(ℝ,B,α) satisfiesE(S(ℝ,B,α)) =C*(ℝ,A,α). WhenG is a Lie group, theC ^∞-elementsC ^∞(A), the analytic elementsC ^ω(A) as well as the entire analytic elementsC ^є(A) carry natural topologies making them algebras with aC*-enveloping algebra. Given a non-unitalC*-algebraA, an inductive system of idealsI _α is constructed satisfyingA =C*-ind limI _α; and the locally convex inductive limit ind limI _α is anm-convex algebra with theC*-enveloping algebraA and containing the Pedersen idealK _a ofA. Given generatorsG with weakly Banach admissible relationsR, we construct universal topological *-algebraA(G, R) and show that it has aC*-enveloping algebra if and only if (G, R) isC*-admissible.     

An upper bound for the adjacent vertex distinguishing acyclic edge chromatic number of a graph

A proper k-edge coloring of a graph G is called adjacent vertex distinguishing acyclic edge coloring if there is no 2-colored cycle in G and the color set of edges incident to u is not equal to the color set of edges incident to υ, where uυ ∈ E(G). The adjacent vertex distinguishing acyclic edge chromatic number of G, denoted by χ′ _aa (G), is the minimal number of colors in an adjacent vertex distinguishing acyclic edge coloring of G. In this paper we prove that if G(V, E) is a graph with no isolated edges, then χ′ _aa (G) ≤ 32Δ. Supported by the Natural Science Foundation of Gansu Province (3ZS051-A25-025)