Testing monotonicity over graph products

We consider the problem of monotonicity testing over graph products. Monotonicity testing is one of the central problems studied in the field of property testing. We present a testing approach that enables us to use known monotonicity testers for given graphs G₁, G₂, to test monotonicity over their product G₁ × G₂. Such an approach of reducing monotonicity testing over a graph product to monotonicity testing over the original graphs, has been previously used in the special case of monotonicity testing over [n]^d for a limited type of testers; in this article, we show that this approach can be applied to allow modular design of testers in many interesting cases: this approach works whenever the functions are boolean, and also in certain cases for functions with a general range. We demonstrate the usefulness of our results by showing how a careful use of this approach improves the query complexity of known testers. Specifically, based on our results, we provide a new analysis for the known tester for [n]^d which significantly improves its query complexity analysis in the low‐dimensional case. For example, when d = O(1), we reduce the best known query complexity from O(log ²n/ε) to O(log n/ε). © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

A multi-dimensional Markov chain and the Meixner ensemble

We show that the transition probability of the Markov chain (G(i,1),...,G(i,n)) _i≥1, where the G(i,j)’s are certain directed last-passage times, is given by a determinant of a special form. An analogous formula has recently been obtained by Warren in a Brownian motion model. Furthermore we demonstrate that this formula leads to the Meixner ensemble when we compute the distribution function for G(m,n). We also obtain the Fredholm determinant representation of this distribution, where the kernel has a double contour integral representation.     

Tilting modules for classical groups and howe duality in positive characteristics

We use the theory of tilting modules for algebraic groups to propose a characteristic free approach to “Howe duality” in the exterior algebra. To any series of classical groups (general linear, symplectic, orthogonal, or spinor) over an algebraically closed field k, we set in correspondence another series of classical groups (usually the same one). Denote byG ₁(m) the group of rankm from the first series and byG ₂(n) the group of rankn from the second series. For any pair (G ₁(m), G₂(n)) we construct theG ₁(m)×G₂(n)-module M(m, n). The construction of M(m, n) is independent of characteristic; for chark=0, the actions ofG ₁(m) andG ₂(n) on M(m, n) form a reductive dual pair in the sense of Howe. We prove that M(m, n) is a tiltingG ₁(m)-andG ₂(n)-module and that End _{G 1}(m) M(m, n) is generated byG ₂(n) and vice versa. The existence of such a module provides much information about the relations between the categoryK ₁(m, n) of rationalG ₁(m)-modules with highest weights bounded in a certain sense byn and the categoryK ₂(m, n) of rationalG ₂(n)-modules with highest weights bounded in the same sense bym. More specifically, we prove that there is a bijection of the set of dominant weights ofG ₁(m)-modules fromK ₁(m, n) to the set of dominant weights ofG ₂(m)-modules fromK ₂(m, n) such that Ext groups for inducedG ₁(m)-modules fromK ₁(m, n) are isomorphic to Ext groups for corresponding Weyl modules overG ₂(n). Moreover, the derived categoriesD ^bK₁(m, n) andD ^bK₂(m, n) appear to be equivalent. We also use our study of the modules M(m, n) to find generators and relations for the algebra of allG-invariants in , whereG=GL _m, Sp_2m, O_m and V is the naturalG-module. Research was supported in part by Grant M7N000/M7N300 from the International Science Foundation and Russian Government and by INTAS Grant 94-4720. Research was supported in part by Grant M8H000/M8H300 from the International Science Foundation and Russian Government and by INTAS Grant 94-4720.     

Maximum chromatic polynomials of 2-connected graphs

In this paper we obtain chromatic polynomials P(G; λ) of 2-connected graphs of order n that are maximum for positive integer-valued arguments λ ≧ 3. The extremal graphs are cycles C_n and these graphs are unique for every λ ≧ 3 and n ≠ 5. We also determine max{P(G; λ): G is 2-connected of order n and G ≠ C_n} and all extremal graphs relative to this property, with some consequences on the maximum number of 3-colorings in the class of 2-connected graphs of order n having _X(G) = 2 and _X(G) = 3, respectively. For every n ≧ 5 and λ ≧ 4, the first three maximum chromatic polynomials of 2-connected graphs are determined.     

Finiteness of integral values for the ratio of two linear recurrences

Let {F(n)} _{n ∈ N} ,{G(n)} _{n ∈ N} , be linear recurrent sequences. In this paper we are concerned with the well-known diophantine problem of the finiteness of the set ? of natural numbers n such that F(n)/G(n) is an integer. In this direction we have for instance a deep theorem of van der Poorten; solving a conjecture of Pisot, he established that if ? coincides with N, then {F(n)/G(n)} _{n ∈ N} is itself a linear recurrence sequence. Here we shall prove that if ? is an infinite set, then there exists a nonzero polynomial P such that P(n)F(n)/G(n) coincides with a linear recurrence for all n in a suitable arithmetic progression. Examples like F(n)=2 ⁿ -2, G(n)=n+2 ⁿ +(-2) ⁿ , show that our conclusion is in a sense best-possible. In the proofs we introduce a new method to cope with a notorious crucial difficulty related to the existence of a so-called dominant root. In an appendix we shall also prove a zero-density result for ? in the cases when the polynomial P cannot be taken a constant. Oblatum 12-XI-2001 & 31-I-2002?Published online: 29 April 2002     

The Augmentation Quotients of the Groups of Order 25, I

In this article we present the nth power Δ ⁿ (G) of the augmentation ideal Δ(G) and describe the structure of Q _n (G) = Δ ⁿ (G)/Δ ⁿ⁺¹(G) for 35 particular groups G of order 2⁵. The structure of Q _n (G) for all the remaining groups of order 2⁵ will be determined in a forthcoming article.     

On the size of graphs labeled with a condition at distance two

A labeling of graph G with a condition at distance two is an integer labeling of V(G) such that adjacent vertices have labels that differ by at least two, and vertices distance two apart have labels that differ by at least one. The lambda-number of G, λ(G), is the minimum span over all labelings of G with a condition at distance two. Let G(n, k) denote the set of all graphs with order n and lambda-number k. In this paper, we examine the sizes of graphs in G(n, k). We modify Chvàtal's result on non-hamiltonian graphs to obtain a formula for the minimum size of a graph in G(n, k), and we use an algorithmic approach to obtain a formula for the maximum size. Finally, we show that for any integer j between the maximum and minimum sizes there exists a graph with size j in G(n, k). © 1996 John Wiley & Sons, Inc.     

Quasirecognition by prime graph of F4(q) where q?=?2n?>?2

The prime graph of a finite group G is denoted by Γ(G). In this paper as the main result, we show that if G is a finite group such that Γ(G) = Γ(F ₄(q)), where q = 2 ⁿ  > 2, then G has a unique nonabelian composition factor isomorphic to F ₄(q). We also show that if G is a finite group satisfying |G| = |F ₄(q)| and Γ(G) = Γ(F ₄(q)), where q = 2 ⁿ  > 2, then G @ F₄(q){G \cong F_4(q)}. As a consequence of our result we give a new proof for a conjecture of Shi and Bi for F ₄(q) where q = 2 ⁿ  > 2.     

On finite groups with non-subnormal subgroups

For a finite group G, let n(G) denote the number of conjugacy classes of non-subnormal subgroups of G. In this paper, we show that a finite group G satisfying n(G)≤2|π(G)| is solvable, and for a finite non-solvable group G, n(G) = 2|π(G)|+1 if and only if G?A₅.     

Equitable coloring of random graphs

An equitable coloring of a graph is a proper vertex coloring such that the sizes of any two color classes differ by at most one. The least positive integer k for which there exists an equitable coloring of a graph G with k colors is said to be the equitable chromatic number of G and is denoted by χ₌(G). The least positive integer k such that for any k′ ≥ k there exists an equitable coloring of a graph G with k′ colors is said to be the equitable chromatic threshold of G and is denoted by χ₌*(G). In this paper, we investigate the asymptotic behavior of these coloring parameters in the probability space G(n,p) of random graphs. We prove that if n^?1/5+? < p < 0.99 for some 0 < ?, then almost surely χ(G(n,p)) ≤ χ₌(G(n,p)) = (1 + o(1))χ(G(n,p)) holds (where χ(G(n,p)) is the ordinary chromatic number of G(n,p)). We also show that there exists a constant C such that if C/n < p < 0.99, then almost surely χ(G(n,p)) ≤ χ₌(G(n,p)) ≤ (2 + o(1))χ(G(n,p)). Concerning the equitable chromatic threshold, we prove that if n^?(1??) < p < 0.99 for some 0 < ?, then almost surely χ(G(n,p)) ≤ χ₌* (G(n,p)) ≤ (2 + o(1))χ(G(n,p)) holds, and if < p < 0.99 for some 0 < ?, then almost surely we have χ(G(n,p)) ≤ χ₌*(G(n,p)) = O_?(χ(G(n,p))). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

A Determinantal Formula for Supersymmetric Schur Polynomials

We derive a new formula for the supersymmetric Schur polynomial s (x/y). The origin of this formula goes back to representation theory of the Lie superalgebra gl(m/n). In particular, we show how a character formula due to Kac and Wakimoto can be applied to covariant representations, leading to a new expression for s (x/y). This new expression gives rise to a determinantal formula for s (x/y). In particular, the denominator identity for gl(m/n) corresponds to a determinantal identity combining Cauchy's double alternant with Vandermonde's determinant. We provide a second and independent proof of the new determinantal formula by showing that it satisfies the four characteristic properties of supersymmetric Schur polynomials. A third and more direct proof ties up our formula with that of Sergeev-Pragacz.     

Some Properties of Bell Groups

For any integer n ≠ 0,1, a group G is said to be “n-Bell” if it satisfies the identity [x ⁿ ,y] = [x,y ⁿ ]. It is known that if G is an n-Bell group, then the factor group G/Z ₂(G) has finite exponent dividing 12n ⁵(n ? 1)⁵. In this article we show that this bound can be improved. Moreover, we prove that every n-Bell group is n-nilpotent; consequently, using results of Baer on finite n-nilpotent groups, we give the structure of locally finite n-Bell groups. Finally, we are concerned with locally graded n-Bell groups for special values of n.     

Codes associated with special linear groups and power moments of multi-dimensional Kloosterman sums

In this paper, we construct the binary linear codes C(SL(n, q)) associated with finite special linear groups SL(n, q), with both n,q powers of two. Then, via the Pless power moment identity and utilizing our previous result on the explicit expression of the Gauss sum for SL(n, q), we obtain a recursive formula for the power moments of multi- dimensional Kloosterman sums in terms of the frequencies of weights in C(SL(n, q)). In particular, when n = 2, this gives a recursive formula for the power moments of Kloosterman sums. We illustrate our results with some examples.     

Total colorings of graphs of order 2n having maximum degree 2n−2

Let χ _t (G) and †(G) denote respectively the total chromatic number and maximum degree of graphG. Yap, Wang and Zhang proved in 1989 that ifG is a graph of orderp having †(G)≥p−4, then χ _t (G≤Δ(G)+2. Hilton has characterized the class of graphG of order 2n having †(G)=2n−1 such that χ _t (G=Δ(G)+2. In this paper, we characterize the class of graphsG of order 2n having †(G)=2n−2 such that χ _t (G=Δ(G)+2 Research supported by National Science Council of the Republic of China (NSC 79-0208-M009-15)     

Linear preservers of orthogonal decomposable Tensors

Let G be a subgroup of the symmetric group S_m and V be an n-dimensional unitary space where nm. Let V(G) be the symmetry class of tensors over V associated with G and the identity character. Let D(G) be the set of all decomposable elements of V(G) and O(G) be its subset consisting of all nonzero decomposable tensors x ₁ ^?…^? x_m such that {x ₁,…,x_m } is an orthogonal set. In this paper we study the structure of linear mappings on V(G) that preserve one of the following subsets: (i)O(G), (ii) D(G)\(O(G)?{0}).     

Some extremal results in cochromatic and dichromatic theory

For a graph G, the cochromatic number of G, denoted z(G), is the least m for which there is a partition of the vertex set of G having order m. where each part induces a complete or empty graph. We show that if {G_n} is a family of graphs where G_n has o(n² log²(n)) edges, then z(G_n) = o(n). We turn our attention to dichromatic numbers. Given a digraph D, the dichromatic number of D is the minimum number of parts the vertex set of D must be partitioned into so that each part induces an acyclic digraph. Given an (undirected) graph G, the dichromatic number of G, denoted d(G), is the maximum dichromatic number of all orientations of G. Let m be an integer; by d(m) we mean the minimum size of all graphs G where d(G) = m. We show that d(m) = θ(m² ln²(m)).     

The Fractional Chromatic Number Of The Categorical Product Of Graphs

We prove that the identity

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.     

On the Validity of Thompson's Conjecture for Finite Simple Groups

In this article, we prove a conjecture of J. G. Thompson for the finite simple group ² D _n (q). More precisely, we show that every finite group G with the property Z(G) = 1 and N(G) = N(² D _n (q)) is necessarily isomorphic to ² D _n (q). Note that N(G) is the set of lengths of conjugacy classes of G.     

The algebra ofG-relations

In this paper, we study a tower {A _n ^G: n} ≥ 1 of finite-dimensional algebras; here, G represents an arbitrary finite group,d denotes a complex parameter, and the algebraA _n ^G(d) has a basis indexed by ‘G-stable equivalence relations’ on a set whereG acts freely and has 2n orbits. We show that the algebraA _n ^G(d) is semi-simple for all but a finite set of values ofd, and determine the representation theory (or, equivalently, the decomposition into simple summands) of this algebra in the ‘generic case’. Finally we determine the Bratteli diagram of the tower {A _n ^G(d): n} ≥ 1 (in the generic case).