On left Hadamard transversals in non-solvable groups

Let G be a group of order 4n and t an involution of G. A 2n-subset R of G is called a left Hadamard transversal of G with respect to 〈t〉 if G=R〈t〉 and for some subsets S₁ and S₂ of G. Let H be a subgroup of G such that G=[G,G]H, t∈H, and t^G⊄H, where t^G is the conjugacy class of t and [G,G] is the commutator subgroup of G. In this article, we show that if R satisfies a condition , then R is a (2n,2,2n,n) relative difference set and one can construct a v×v integral matrix B such that BB^T=B^TB=(n/2)I, where v is a positive integer determined by H and t^G (see Theorem 2.6). Using this we show that there is no left Hadamard transversal R satisfying (*) in some simple groups.     

Diagonal norm hermitian matrices

If v is a norm on $\text{C}$ⁿ, let H(v) denote the set of all norm-Hermitians in $\text{C}$ⁿⁿ. Let S be a subset of the set of real diagonal matrices D. Then there exists a norm v such that S=H(v) (or S = H(v)∩D) if and only if S contains the identity and S is a subspace of D with a basis consisting of rational vectors. As a corollary, it is shown that, for a diagonable matrix h with distinct eigenvalues λ₁,…, λ_r, r?n, there is a norm v such that h ∈ H(v), but h^s?H(v), for some integer s, if and only if λ₂–λ₁,…, λ_r–λ₁ are linearly dependent over the rationals. It is also shown that the set of all norms v, for which H(v) consists of all real multiples of the identity, is an open, dense subset, in a natural metric, of the set of all norms.     

Eccentric sequences and eccentric sets in graphs

By a graph we mean a finite undirected connected graph of order p, p ? 2, with no loops or multiple edges. A finite non-decreasing sequence S: s₁, s₂, …, s_p, p ? 2, of positive integers is an eccentric sequence if there exists a graph G with vertex set V(G) = {v₁, v₂, …, v_p} such that for each i, 1 ? i ? p, s, is the eccentricity of v₁. A set S is an eccentric set if there exists a graph G such that the eccentricity ρ(v₁) is in S for every v₁ ? V(G), and every element of S is the eccentricity of some vertex in G. In this note we characterize eccentric sets, and we find the minimum order among all graphs whose eccentric set is a given set, to obtain a new necessary condition for a sequence to be eccentric. We also present some properties of graphs having preassigned eccentric sequences.     

A new result on Davenport constant

Let G be a finite abelian group of order n and Davenport constant D(G). Let S=⁰h(S)_∏g∈Ggvg(S)∈F(G) be a sequence with a maximal multiplicity h(S) attained by 0 and t=|S|?n+D(G)−1. Then 0∈k_∑(S) for every 1?k?t+1−D(G). This is a refinement of the fundamental result of Gao [W.D. Gao, A combinatorial problem on finite abelian groups, J. Number Theory 58 (1996) 100-103].     

A matrix of combinatorial numbers related to the symmetric groups

For permutation groups G of finite degree we define numbers t_B(G)=|G|^-1∑_R∈G∏₁(1a₁(g))^b_i, where B=(b₁,…,b₁) is a tuple of non-negative integers and a₁(g) denotes the number of i cycles in the element g. We show that t_B(G) is the number of orbits of G, acting on a set Δ_B(G) of tuples of matrices. In the case G=S_n we get a natural interpretation for combinatorial numbers connected with the Stiring numbers of the second kind.     

Conjugate transforms for τT semigroups of probability distribution functions

This paper introduces the use of conjugate transforms in the study of τ_T semigroups of probability distribution functions. If Δ⁺ denotes the space of one-dimensional distribution functions concentrated on [0, ∞) and T is a t-norm, i.e., a suitable binary operation on [0, 1], then the operation τ_T is defined for F, G in Δ⁺by τ_T(F, G)(x) = sup_{u+v = x}T(F(u), G(v)) for all x. The pair (Δ⁺, τ_T) is then a semigroup. For any Archimedean t-norm T, a conjugate transform C_T is defined on (Δ⁺, τ_T). These transforms are shown to play a role similar to that played by the Laplace transform on the convolution semigroup. Thus a theory of “characteristic functions” for τ_T semigroups is developed. In addition to establishing their basic algebraic properties, we also use conjugate transforms to study the algebraic questions of the cancellation law, infinitely divisible elements, and solutions of equations in τ_T semigroups.     

On subgraph number independence in trees

For finite graphs F and G, let N_F(G) denote the number of occurrences of F in G, i.e., the number of subgraphs of G which are isomorphic to F. If $\text{F}$ and $\text{G}$ are families of graphs, it is natural to ask then whether or not the quantities N_F(G), F∈$\text{F}$, are linearly independent when G is restricted to $\text{G}$. For example, if $\text{F}$ = {K₁, K₂} (where K_n denotes the complete graph on n vertices) and $\text{F}$ is the family of all (finite) trees, then of course N_K1(T) ? N_K2(T) = 1 for all T∈$\text{F}$. Slightly less trivially, if $\text{F}$ = {S_n: n = 1, 2, 3,…} (where S_n denotes the star on n edges) and $\text{G}$ again is the family of all trees, then Σ_n=1^∞(?1)ⁿ⁺¹N_Sn(T)=1 for all T∈$\text{G}$. It is proved that such a linear dependence can never occur if $\text{F}$ is finite, no F∈$\text{F}$ has an isolated point, and $\text{G}$ contains all trees. This result has important applications in recent work of L. Lovász and one of the authors (Graham and Lovász, to appear).     

Simultaneous orderings in function fields

For every Dedekind domain R, Bhargava defined the factorials of a subset S of R by introducing the notion of p-ordering of S, for every maximal ideal p of R. We study the existence of simultaneous ordering in the case S=R=O_K, where O_K is the ring of integers of a function field K over a finite field F_q. We show, that when O_K is the ring of integers of an imaginary quadratic extension K of F_q(T), K=F_q(T)/(Y²-D(T)), then there exists a simultaneous ordering if and only if degD?1.     

Oscillatory properties of strongly superlinear differential equations with deviating arguments

We regard a graph G as a set {1,…, v} together with a nonempty set E of two-element subsets of {1,…, v}. Let p = (p₁,…, p_v) be an element of $\text{R}$^nv representing v points in $\text{R}$ⁿ and consider the realization G(p) of G in $\text{R}$ⁿ consisting of the line segments [p_i, p_j] in $\text{R}$ⁿ for {i, j} ?E. The figure G(p) is said to be rigid in $\text{R}$ⁿ if every continuous path in $\text{R}$^nv, beginning at p and preserving the edge lengths of G(p), terminates at a point q ? $\text{R}$^nv which is the image (Tp₁,…, Tp_v) of p under an isometry T of $\text{R}$ⁿ. We here study the rigidity and infinitesimal rigidity of graphs, surfaces, and more general structures. A graph theoretic method for determining the rigidity of graphs in $\text{R}$² is discussed, followed by an examination of the rigidity of convex polyhedral surfaces in $\text{R}$³.     

Elasticity of factorizations in R 0 + X R1 + … + X lRl [X]

For an atomic domain R the elasticity ρ(R) is defined by ρ(R) = sup{m/n ¦ u₁ … u _m = v ₁ … v_n where u_i, v_i ∈ R are irreducible}. Let R ₀ ? … ? R _l be an ascending chain of domains which are finitely generated over ? and assume that R _l is integral over R ₀. Let X be an indeterminate. In this paper we characterize all domains D of the form D = R ₀ + XR₁ + … + X^lR_l[X] whose elasticity ρ(D) is finite.     

Isomorphism of circulant graphs and digraphs

Let S? {1, …, n?1} satisfy ?S = S mod n. The circulant graph G(n, S) with vertex set {v₀, v₁,…, v_n?1} and edge set E satisfies v_iv_j?E if and only if j ? i ∈ S, where all arithmetic is done mod n. The circulant digraph G(n, S) is defined similarly without the restriction S = ? S. Ádám conjectured that $\text{G(n, S) ? G(n, S′)}$ if and only if S = uS′ for some unit u mod n. In this paper we prove the conjecture true if n = pq where p and q are distinct primes. We also show that it is not generally true when n = p², and determine exact conditions on S that it be true in this case. We then show as a simple consequence that the conjecture is false in most cases when n is divisible by p² where p is an odd prime, or n is divisible by 2⁴.     

Independent edges in bipartite graphs obtained from orientations of graphs

Given a digraph D on vertices v₁, v₂, ?, v_n, we can associate a bipartite graph B(D) on vertices s₁, s₂, ?, s_n, t₁, t₂, ?, t_n, where s_it_j is an edge of B(D) if (v_i, v_j) is an arc in D. Let O_G denote the set of all orientations on the (undirected) graph G. In this paper we will discuss properties of the set S(G) := {β₁ (B(D))) | D ? O_G}, where β₁ is the edge independence number. In the first section we present some background and related concepts. We show that sets of the form S(G) are convex and that max S(G) ≦ 2 min S(G). Furthermore, this completely characterizes such sets. In the second section we discuss some bounds on elements of S(G) in terms of more familiar graphical parameters. The third section deals with extremal problems. We discuss bounds on elements of S(G) if the order and size of G are known, particularly when G is bipartite. In this section we exhibit a relation between max S(G) and the concept of graphical closure. In the fourth and final section we discuss the computational complexity of computing min S(G) and max S(G). We show that the first problem is NP-complete and that the latter is polynomial.     

Atomic subspaces of {L_1}-martingale spaces

In Part I of the present paper the following problem was investigated. Let G be a finite simple graph, and S be a finite set of primes. We say that G is representable with S if it is possible to attach rational numbers to the vertices of G such that the vertices v₁, v₂ are connected by an edge if and only if the difference of the attached values is an S-unit. In Part I we gave several results concerning the representability of graphs in the above sense.     

The hull and geodetic numbers of orientations of graphs

For an oriented graph D, let I_D[u,v] denote the set of all vertices lying on a u-v geodesic or a v-u geodesic. For S⊆V(D), let I_D[S] denote the union of all I_D[u,v] for all u,v∈S. Let [S]_D denote the smallest convex set containing S. The geodetic number g(D) of an oriented graph D is the minimum cardinality of a set S with I_D[S]=V(D) and the hull number h(D) of an oriented graph D is the minimum cardinality of a set S with [S]_D=V(D). For a connected graph G, let O(G) be the set of all orientations of G, define g⁻(G)=min{g(D):D∈O(G)}, g⁺(G)=max{g(D):D∈O(G)}, h⁻(G)=min{h(D):D∈O(G)}, and h⁺(G)=max{h(D):D∈O(G)}. By the above definitions, h⁻(G)≤g⁻(G) and h⁺(G)≤g⁺(G). In the paper, we prove that g⁻(G)<h⁺(G) for a connected graph G of order at least 3, and for any nonnegative integers a and b, there exists a connected graph G such that g⁻(G)−h⁻(G)=a and g⁺(G)−h⁺(G)=b. These results answer a problem of Farrugia in [A. Farrugia, Orientable convexity, geodetic and hull numbers in graphs, Discrete Appl. Math. 148 (2005) 256-262].     

The distribution of Brownian motion in Rn at a natural stopping time

For a measure μ on Rⁿ let ((B_t, P^μ) be Brownian motion in Rⁿ with initial distribution μ. Let D be an open subset of Rⁿ with exit time ζ ≡ inf {t > 0: B_t ? D}. In the case where D is a Green region with Green function G and μ is a measure in D such that G_μ is not identically infinite on any component of D, we have given necessary and sufficient conditions for a measure ν in D to be of the form ν(dx) = P^μ(B_T ? dx, T <ζ), where T is some natural stopping time for (B_t), and we have applied this characterization to show that a measure ν in D satisfies G_ν ? G_μ iff ν is of the form ν(dx) = P^α(B_T ? dx, T <ζ) + β(dx), where T is some natural stopping time for (B_t) and α and β are measures in D such that α + β = μ and β lives on a polar set. We have proved analogous results in the case where D = R² and μ is a finite measure on R² such that ∫ log⁺ ∥x∥ du(x) < ∞, and applied this to give a characterization of the stopping times T for Brownian motion in R² such that (log⁺ ∥B_T∧t∥)_0<t<∞ is P^μ-uniformly integrable.     

The vertex linear arboricity of distance graphs

A distance graph is a graph G(R,D) with the set of all points of the real line as vertex set and two vertices u,v∈R are adjacent if and only if |u-v|∈D where the distance set D is a subset of the positive real numbers. Here, the vertex linear arboricity of G(R,D) is determined when D is an interval between 1 and δ. In particular, the vertex linear arboricity of integer distance graphs G(D) is discussed, too.     

The fundamental constituents of iteration digraphs of finite commutative rings

For a finite commutative ring R and a positive integer k ? 2, we construct an iteration digraph G(R, k) whose vertex set is R and for which there is a directed edge from a ∈ R to b ∈ R if b = a ^k . Let R = R ₁ ⊕ … ⊕ R _s , where s > 1 and R _i is a finite commutative local ring for i ∈ {1, …, s}. Let N be a subset of {R ₁, …, R _s } (it is possible that N is the empty set \(\not 0\) ). We define the fundamental constituents G _N ^* (R, k) of G(R, k) induced by the vertices which are of the form {(a ₁, …, a _s ) ∈ R: a _i ∈ D(R _i ) if R _i ∈ N, otherwise a _i ∈ U(R _i ), i = 1, …, s}, where U(R) denotes the unit group of R and D(R) denotes the zero-divisor set of R. We investigate the structure of G* _N (R, k) and state some conditions for the trees attached to cycle vertices in distinct fundamental constituents to be isomorphic.     

Convexity in oriented graphs

For vertices u and v in an oriented graph D, the closed interval I[u,v] consists of u and v together with all vertices lying in a u−v geodesic or v−u geodesic in D. For S⊆V(D), I[S] is the union of all closed intervals I[u,v] with u,v∈S. A set S is convex if I[S]=S. The convexity number con(D) is the maximum cardinality of a proper convex set of V(D). The nontrivial connected oriented graphs of order n with convexity number n−1 are characterized. It is shown that there is no connected oriented graph of order at least 4 with convexity number 2 and that every pair k, n of integers with 1⩽k⩽n−1 and k≠2 is realizable as the convexity number and order, respectively, of some connected oriented graph. For a nontrivial connected graph G, the lower orientable convexity number con⁻(G) is the minimum convexity number among all orientations of G and the upper orientable convexity number con⁺(G) is the maximum such convexity number. It is shown that con⁺(G)=n−1 for every graph G of order n⩾2. The lower orientable convexity numbers of some well-known graphs are determined, with special attention given to outerplanar graphs.     

Frame cellular automata: Configurations, generating sets and related matroids

We introduce a frame cellular automaton as a broad generalization of an earlier study on quasigroup-defined cellular automata. It consists of a triple (F,R,E_F) where, for a given finite set X of cells, the frame F is a family of subsets of X (called elementary frames, denoted S_i, i=1,…,n), which is a cover of X. A matching configuration is a map which attributes to each cell a state in a finite set G under restriction of a set of local rules R={R_i∣i=1,…n}, where R_i holds in the elementary frame S_i and is determined by an (|S_i|-1)-ary quasigroup over G. The frame associated map E_F models how a matching configuration can be grown iteratively from a certain initial cell-set. General properties of frames and related matroids are investigated. A generating set S⊂X is a set of cells such that there is a bijection between the collection of matching configurations and G^S. It is shown that for certain frames, the algebraically defined generating sets are bases of a related geometric-combinatorially defined matroid.     

Algebraic properties of codimension series of PI-algebras

Let c _n (R), n = 0, 1, 2, …, be the codimension sequence of the PI-algebra R over a field of characteristic 0 with T-ideal T(R) and let c(R, t) = c ₀(R) + c ₁(R)t + c ₂(R)t ² + … be the codimension series of R (i.e., the generating function of the codimension sequence of R). Let R ₁,R ₂ and R be PI-algebras such that T(R) = T(R1)T(R ₂). We show that if c(R ₁, t) and c(R ₂, t) are rational functions, then c(R, t) is also rational. If c(R ₁, t) is rational and c(R ₂, t) is algebraic, then c(R, t) is also algebraic. The proof is based on the fact that the product of two exponential generating functions behaves as the exponential generating function of the sequence of the degrees of the outer tensor products of two sequences of representations of the symmetric groups S _n .