Odd‐angulated graphs and cancelling factors in box products

Under what conditions is it true that if there is a graph homomorphism G □ H → G □ T, then there is a graph homomorphism H→ T? Let G be a connected graph of odd girth 2k + 1. We say that G is (2k + 1)‐angulated if every two vertices of G are joined by a path each of whose edges lies on some (2k + 1)‐cycle. We call G strongly (2k + 1)‐angulated if every two vertices are connected by a sequence of (2k + 1)‐cycles with consecutive cycles sharing at least one edge. We prove that if G is strongly (2k + 1)‐angulated, H is any graph, S, T are graphs with odd girth at least 2k + 1, and ?: G□ H→S□T is a graph homomorphism, then either ? maps G□{h} to S□{t_h} for all h∈V(H) where t_h∈V(T) depends on h; or ? maps G□{h} to {s_h}□ T for all h∈V(H) where s_h∈V(S) depends on h. This theorem allows us to prove several sufficient conditions for a cancelation law of a graph homomorphism between two box products with a common factor. We conclude the article with some open questions. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:221‐238, 2008     

Words and Polynomial Invariants of Finite Groups in Non-Commutative Variables

Let V be a complex vector space with basis {x ₁, x ₂, . . . , x _n } and G be a finite subgroup of GL(V). The tensor algebra T(V) over the complex is isomorphic to the polynomials in the non-commutative variables x ₁, x ₂, . . . , x _n with complex coefficients. We want to give a combinatorial interpretation for the decomposition of T(V) into simple G-modules. In particular, we want to study the graded space of invariants in T(V) with respect to the action of G. We give a general method for decomposing the space T(V) into simple modules in terms of words in a Cayley graph of the group G. To apply the method to a particular group, we require a homomorphism from a subalgebra of the group algebra into the character algebra. In the case of G as the symmetric group, we give an example of this homomorphism from the descent algebra. When G is the dihedral group, we have a realization of the character algebra as a subalgebra of the group algebra. In those two cases, we have an interpretation for the graded dimensions and the number of free generators of the algebras of invariants in terms of those words.     

ON SYMMETRIC UNITS IN GROUP ALGEBRAS

Let U(KG) be the group of units of the group ring KG of the group G over a commutative ring K. The anti-automorphism g → g ^?1 of G can be extended linearly to an anti-automorphism a → a ^* of KG. Let S _* (KG) = {x ∈ U(KG) | x ^* = x} be the set of all symmetric units of U(KG). We consider the following question: for which groups G and commutative rings K it is true that S _* (KG) is a subgroup in U(KG). We answer this question when either a) G is torsion and K is a commutative G-favourable integral domain of characteristic p≥ 0 or b) G is non-torsion nilpotent group and KG is semiprime.     

Weighted scattering matrices of regular coverings of graphs

We give a decomposition formula for the determinant det(I ? U(λ)) of the weighted bond scattering matrix U(λ) of a regular covering of G. Furthermore, we define an L-function of G, and give a determinant expression of it. As a corollary, we express some determinant of the weighted bond scattering matrix of a regular covering of G by means of its L-functions.     

Undirected power graphs of semigroups

The undirected power graph G(S) of a semigroup S is an undirected graph whose vertex set is S and two vertices a,b∈S are adjacent if and only if a≠b and a ^m =b or b ^m =a for some positive integer m. In this paper we characterize the class of semigroups S for which G(S) is connected or complete. As a consequence we prove that G(G) is connected for any finite group G and G(G) is complete if and only if G is a cyclic group of order 1 or p ^m . Particular attention is given to the multiplicative semigroup ℤ _n and its subgroup U _n , where G(U _n ) is a major component of G(ℤ _n ). It is proved that G(U _n ) is complete if and only if n=1,2,4,p or 2p, where p is a Fermat prime. In general, we compute the number of edges of G(G) for a finite group G and apply this result to determine the values of n for which G(U _n ) is planar. Finally we show that for any cyclic group of order greater than or equal to 3, G(G) is Hamiltonian and list some values of n for which G(U _n ) has no Hamiltonian cycle.     

Davenport constant for semigroups

Let G be a finite commutative semigroup. The Davenport constant of G is the smallest integer d such that, every sequence S of d elements in G contains a subsequence T (≠S) with the same product of S. Let . Among other results, we determine D(R ^×)−D(U(R)), where R ^× is the multiplicative semigroup of R and U(R) is the group of units of R.     

The cycle space of an embedded graph

Let G be a connected graph with edge set E embedded in the surface ∑. Let G° denote the geometric dual of G. For a subset d of E, let τd denote the edges of G° that are dual to those edges of G in d. We prove the following generalizations of well-known facts about graphs embedded in the plane. (1) b is a boundary cycle in G if and only if τb is a cocycle in G°. (2) If T is a spanning tree of G, then τ(E/T) contains a spanning tree of G°. (3) Let T be any spanning tree of G and, for e ? E/T, let T(e) denote the fundamental cycle of e. Let U ∪ E/T. Then τU is a spanning tree of G° if and only if the set of face boundaries, less any one, together with the set {T(e); e ? E/(T ∪ U)} is a basis for the cycle space of G.     

Trees with Equal Domination and Restrained Domination Numbers

Let G = (V,E) be a graph and let S V. The set S is a packing in G if the vertices of S are pairwise at distance at least three apart in G. The set S is a dominating set (DS) if every vertex in V − S is adjacent to a vertex in S. Further, if every vertex in V − S is also adjacent to a vertex in V − S, then S is a restrained dominating set (RDS). The domination number of G, denoted by γ(G), is the minimum cardinality of a DS of G, while the restrained domination number of G, denoted by γ_r(G), is the minimum cardinality of a RDS of G. The graph G is γ-excellent if every vertex of G belongs to some minimum DS of G. A constructive characterization of trees with equal domination and restrained domination numbers is presented. As a consequence of this characterization we show that the following statements are equivalent: (i) T is a tree with γ(T)=γ_r(T); (ii) T is a γ-excellent tree and T ≠ K₂; and (iii) T is a tree that has a unique maximum packing and this set is a dominating set of T. We show that if T is a tree of order n with ℓ leaves, then γ_r(T) ≤ (n + ℓ + 1)/2, and we characterize those trees achieving equality.     

Reduction of structure for torsors over semilocal rings

Let G be a reductive affine group scheme defined over a semilocal ring k. Assume that either G is semisimple or k is normal and noetherian. We show that G has a finite k-subgroup S such that the natural map H ¹(R, S) → H ¹(R, G) is surjective for every semilocal ring R containing k. In other words, G-torsors over Spec(R) admit reduction of structure to S. We also show that the natural map H ¹(X, S) → H ¹(X, G) is surjective in several other contexts, under suitable assumptions on the base ring k, the scheme X/k and the group scheme G/k. These results have already been used to study loop algebras and essential dimension of connected algebraic groups in prime characteristic. Additional applications are presented at the end of this paper. V. Chernousov was partially supported by the Canada Research Chairs Program and an NSERC research grant. Z. Reichstein was partially supported by NSERC Discovery and Accelerator Supplement grants.     

Connectivity properties of horospheres in Euclidean buildings and applications to finiteness properties of discrete groups

Let G(O_S)\mathbf{G}(\mathcal{O}_{S}) be an S-arithmetic subgroup of a connected, absolutely almost simple linear algebraic group G over a global function field K. We show that the sum of local ranks of G determines the homological finiteness properties of G(O_S)\mathbf{G}(\mathcal{O}_{S}) provided the K-rank of G is 1. This shows that the general upper bound for the finiteness length of G(O_S)\mathbf{G}(\mathcal{O}_{S}) established in an earlier paper is sharp in this case.     

Homomorphisms of graphs into odd cycles

We give a class of graphs G for which there exists a homomorphism (= adjacency preserving map) from V(G) to V(C), where C is the shortest odd cycle in G, thereby extending a result of Albertson, Catlin, and Gibbons. Our class of graphs is characterized by the following property: For each odd subdivision G′ of G there exists a homomorphic map from V(G′) to V(C), where C′ is the shortest odd cycle of G′.     

Spanning trees with leaf distance at least four

For a graph G, we denote by i(G) the number of isolated vertices of G. We prove that for a connected graph G of order at least five, if i(G–S) < |S| for all ?? ≠ S ? V(G), then G has a spanning tree T such that the distance in T between any two leaves of T is at least four. This result was conjectured by Kaneko in “Spanning trees with constrains on the leaf degree”, Discrete Applied Math, 115 (2001), 73–76. Moreover, the condition in the result is sharp in a sense that the condition i(G–S) < |S| cannot be replaced by i(G–S) ≤ |S|. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 83–90, 2007     

Every T-space is equivalent to a T-space of continuous functions

A T-space U of degree k is a (k + 1)-dimensional vector space over (the real line) of real-valued functions defined on a linearly ordered set, satisfying the condition: for every nonzero u ε U, Z(u), the number of distinct zeros of u and ^-(u), the number of alternations in sign of u(t) with increasing t, each do not exceed k. It is demonstrated that given a T-space U of degree k > 0 on an arbitrary linearly ordered set T, there is a subset T′ of the real line and a nonsingular linear map L:U→ C(T′), the set of continuous functions on T′, such that the following hold: L(U) is a T-space of degree k; for u ε U, Z(u) = Z(L(u)), S^−(u) = S^−(L(u); and for some order-preserving bijection Θ:T → T′, u(t) = O if and only if L(u)(Θ(t) = 0. It is also shown that a T-space on a subset T can be extended to a T-space on the closure of T in ]inf T, sup T], provided that there are no “interval gaps” in T. Examples show that, in general, a T-space cannot be extended across an “interval gap” in its domain, and cannot be extended to both the infimum and supremum of its domain. Conditions for a T-space to be Markov, and to admit an adjoined function are derived.     

Fields interpretable in rosy theories

We are working in a monster model ℭ of a rosy theory T. We prove the following theorems, generalizing the appropriate results from the finite Morley rank case and o-minimal structures. If R is a ⋁-definable integral domain of positive, finite U^t-rank, then its field of fractions is interpretable in ℭ. If A and M are infinite, definable, abelian groups such that A acts definably and faithfully on M as a group of automorphisms, M is A-minimal and U^t(M) is finite, then there is an infinite field interpretable in ℭ. If G is an infinite, solvable but non nilpotent-by-finite, definable group of finite U^t-rank and T has NIP, then there is an infinite field interpretable in 〈G, ·〉.     

The Relative Brauer Group of an Affine Double Plane

We study algebra classes and divisor classes on a normal affine surface of the form z ² = f(x, y). The affine coordinate ring is T = k[x, y, z]/(z ² ? f), and if R = k[x, y][f ^?1] and S = R[z]/(z ² ? f), then S is a quadratic Galois extension of R. If the Galois group is G, we show that the natural map H¹(G, Cl(T)) → H¹(G, Pic(S)) factors through the relative Brauer group B(S/R) and that all of the maps are onto. Sufficient conditions are given for H¹(G, Cl(T)) to be isomorphic to B(S/R). The groups and maps are computed for several examples.     

A Boolean algebra of characteristic subgroups of a finite group

We construct a “natural” sublattice L(G) of the lattice of all of those subgroups of a finite group G that contain the Frattini subgroup F(G){\Phi(G)} . We show that L(G) is a Boolean algebra, and that its members are characteristic subgroups of G. If F(G){\Phi(G)} is trivial, then L(G) is exactly the set of direct factors U of G such that U and G/U have no common nontrivial homomorphic image.     

Twisted Automorphisms and Twisted Right Gyrogroups

In this paper we make an attempt to study right loops (S, o) in which, for each y ∈ S, the map σ _y from the inner mapping group G _S of (S, o) to itself given by σ _y (h)(x)o h(y) = h(xoy), x ∈ S, h ∈ G _S is a homomorphism. The concept of twisted automorphisms of a right loop and also the concept of twisted right gyrogroup appears naturally and it turns out that the study is almost equivalent to the study of twisted automorphisms and a twisted right gyrogroup. We also study relationship between twisted gyrotransversals and twisted subgroups.     

Non‐Abelian homomorphism testing,and distributions close to their self‐convolutions

In this paper, we study two questions related to the problem of testing whether a function is close to a homomorphism. For two finite groups G,H (not necessarily Abelian), an arbitrary map f : G,H, and a parameter 0 < ε < 1, say that f is ε‐close to a homomorphism if there is some homomorphism g such that g and f differ on at most ε | G | elements of G, and say that f is ε‐far otherwise. For a given f and ε, a homomorphism tester should distinguish whether f is a homomorphism, or if f is ε‐far from a homomorphism. When G is Abelian, it was known that the test which picks O(1/ε) random pairs x,y and tests that f(x) + f(y) = f(x + y) gives a homomorphism tester. Our first result shows that such a test works for all groups G. Next, we consider functions that are close to their self‐convolutions. Let A = {a_g | g ε G} be a distribution on G. The self‐convolution of A, A^′ = {a | g ε G}, is defined by It is known that A= A^′ exactly when A is the uniform distribution over a subgroup of G. We show that there is a sense in which this characterization is robust—that is, if A is close in statistical distance to A^′, then A must be close to uniform over some subgroup of G. Finally, we show a relationship between the question of testing whether a function is close to a homomorphism via the above test and the question of characterizing functions that are close to their self‐convolutions. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008