Optimal labelling of a product of two paths

If G is a graph with p vertices and at least one edge, we set φ (G) = m n max |f(u) ? f(v)|, where the maximum is taken over all edges uv and the minimum over all one-to-one mappings f : V(G) → {1, 2, …, p}: V(G) denotes the set of vertices of G.P_n will denote a path of length n whose vertices are integers 1, 2, …, n with i adjacent to j if and only if |i ? j| = 1. P_m × P_n will denote a graph whose vertices are elements of {1, 2, …, m} × {1, 2, …, n} and in which (i, j), (r, s) are adjacent whenever either i = r and |j ? s| = 1 or j = s and |i ? r| = 1.Theorem.If max(m, n) ? 2, thenφ(P_m × P_n) = min(m, n).     

Minimizing and maximizing the diameter in orientations of graphs

For a graph G, letG′(G″) denote an orientation ofG having maximum (minimum respectively) finite diameter. We show that the length of the longest path in any 2-edge connected (undirected) graph G is precisely diam(G′). LetK(m _l ,m ₂,...,m _n) be the completen-partite graph with parts of cardinalitiesm ₁ m₂, …,m _n . We prove that ifm ₁ = m₂ = … =m _n = m,n ≥ 3, then diam(K″(m₁,m₂,...,m_n)) = 2, unless m=1 andn = 4.     

Multiplicative infinite loop space theory

Let G be a finitely presented group given by its pre-abelian presentation <X1,…,Xm; Xe11ζ1,…,Xemmζ,ζm+1,…>, where ei≥0 for i = 1,…, m and ζj?G′ for j≥1. Let N be the subgroup of G generated by the normal subgroups [xeii, G] for i = 1,…, m. Then Dn+2(G)≡γn+2(G) (modNG′) for all n≥0, where G” is the second commutator subgroup of G,γn+2(G) is the (n+2)th term of the lower central series of G and Dn+2(G) = G∩(1+△n+2(G)) is the (n+2)th dimension subgroup of G.     

Some results on starlike trees and sunlike graphs

A tree is called starlike if it has exactly one vertex of degree greater than two. In [4] it was proved that two starlike treesG andH are cospectral if and only if they are isomorphic. We prove here that there exist no two non-isomorphic Laplacian cospectral starlike trees. Further, letG be a simple graph of ordern with vertex setV(G)={1,2, …,n} and letH={H ₁,H ₂, ...H _n } be a family of rooted graphs. According to [2], the rooted productG(H) is the graph obtained by identifying the root ofH _i with thei-th vertex ofG. In particular, ifH is the family of the paths $P_{k_1 } , P_{k_2 } , ..., P_{k_n } $ with the rooted vertices of degree one, in this paper the corresponding graphG(H) is called the sunlike graph and is denoted byG(k ₁,k ₂, …,k _n ). For any (x ₁,x ₂, …,x _n ) ∈I _* ⁿ , whereI _*={0,1}, letG(x ₁,x ₂, …,x _n ) be the subgraph ofG which is obtained by deleting the verticesi ₁, i₂, …,i _j ∈ V(G) (0≤j≤n), provided that $x_{i_1 } = x_{i_2 } = ... = x_{i_j } = 0$ . LetG(x ₁,x ₂,…, x _n] be the characteristic polynomial ofG(x ₁,x ₂,…, x _n ), understanding thatG[0, 0, …, 0] ≡ 1. We prove that $$G[k_1 , k_2 ,..., k_n ] = \Sigma _{x \in ^{I_ * ^n } } \left[ {\Pi _{i = 1}^n P_{k_i + x_i - 2} (\lambda )} \right]( - 1)^{n - (\mathop \Sigma \limits_{i = 1}^n x_i )} G[x_1 , x_2 , ..., x_n ]$$ where x=(x ₁,x ₂,…,x _n );G[k ₁,k ₂,…,k _n ] andP _n (γ) denote the characteristic polynomial ofG(k ₁,k ₂,…,k _n ) andP _n , respectively. Besides, ifG is a graph with λ₁(G)≥1 we show that λ₁(G)≤λ₁(G(k ₁,k ₂, ...,k _n )) < for all positive integersk ₁,k ₂,…,k _n , where λ₁ denotes the largest eigenvalue.     

Prime interchange graphs of classes of matrices of zeros and ones

Let R = (r₁,…, r_m) and S = (s₁,…, s_n) be nonnegative integral vectors, and let $\text{U}$(R, S) denote the class of all m × n matrices of 0's and 1's having row sum vector R and column sum vector S. An invariant position of $\text{U}$(R, S) is a position whose entry is the same for all matrices in $\text{U}$(R, S). The interchange graph G(R, S) is the graph where the vertices are the matrices in $\text{U}$(R, S) and where two matrices are joined by an edge provided they differ by an interchange. We prove that when 1 ≤ r_i ≤ n ? 1 (i = 1,…, m) and 1 ≤ s_j ≤ m ? 1 (j = 1,…, n), G(R, S) is prime if and only if $\text{U}$(R, S) has no invariant positions.     

On an approximation property for nondiscrete inequivalent representations of finitely generated groups

Let R(Γ, G) be the variety of representations of a finitely generated group Γ in a simple complex algebraic group G. We establish some sufficient conditions for the image of the diagonal representation ϱ = (ϱ₁, …, ϱ_t), ϱ_i ε R(Γ, G), to be dense in G^f in the complex topology (“weak approximation”).     

Weighted rational approximation in the complex plane

Given a triple (G, W, γ) of an open bounded set G in the complex plane, a weight function W(z) which is analytic and different from zero in G, and a number γ with 0 ≤ γ ≤ 1, we consider the problem of locally uniform rational approximation of any function ƒ(z), which is analytic in G, by weighted rational functions W^m_i+n_i(z)R_mi, n_i(z)_{i = 0}^∞, where R_mi, n_i(z) = P_mi(z)/Q_ni(z) with deg P_mi ≤ m_i and deg Q_ni ≤ n_i for all i ≥ 0 and where m_i + n_i → ∞ as i → ∞ such that lim m_i/[m_i + n_i] = γ. Our main result is a necessary and sufficient condition for such an approximation to be valid. Applications of the result to various classical weights are also included.     

A polynomial dual of partitions

Let P(x) = Σ_i=0ⁿa_ixⁱ be a nonnegative integral polynomial. The polynomial P(x) is m-graphical, and a multi-graph G a realization of P(x), provided there exists a multi-graph G containing exactly P(1) points where a_i of these points have degree i for 0≤i≤n. For multigraphs G, H having polynomials P(x), Q(x) and number-theoretic partitions (degree sequences) π, ?, the usual product P(x)Q(x) is shown to be the polynomial of the Cartesian product G × H, thus inducing a natural product π? which extends that of juxtaposing integral multiple copies of ?. Skeletal results are given on synthesizing a multi-graph G via a natural Cartesian product G₁ × … × G_k having the same polynomial (partition) as G. Other results include an elementary sufficient condition for arbitrary nonnegative integral polynomials to be graphical.     

On cyclic decompositions of the complete graph into the 2-regular graphs

The symbol C(m₁ ⁿ ₁m₂ ⁿ ₂...m_s ⁿ _s) denotes a 2-regular graph consisting ofn _i cycles of lengthm _i , i=1, 2,…,s. In this paper, we give some construction methods of cyclic(K _v ,G)-designs, and prove that there exists a cyclic(K _v , G)-design whenG=C((4m ₁) ⁿ ₁(4m ₂) ⁿ ₂...(4m _s ) ⁿ _s andv ≡ 1 (mod 2¦G¦).     

Grothendieck groups of abelian group rings

Let R be a noetherian ring, and G(R) the Grothendieck group of finitely generated modules over R. For a finite abelian group π, we describe G(Rπ) as the direct sum of groups G(R'). Each R' is the form R[ζ_n, 1/n], where n is a positive integer and ζ_n a primitive nth root of unity. As an application, we describe the structure of the Grothendiek group of pairs (H, u), where H is an abelian group and u is an automorphism of H of finite order.     

A subdeterminant inequality for normal matrices

Let A be an n × n normal matrix over $\text{C}$, and Q_m, _n be the set of strictly increasing integer sequences of length m chosen from 1,…,n. For α, β ? Q_m, _n denote by A[α|β] the submatrix obtained from A by using rows numbered α and columns numbered β. For k ? {0, 1,…, m} we write |α∩β| = k if there exists a rearrangement of 1,…, m, say i₁,…, i_k, i_k+1,…, i_m, such that α(i_j) = β(i_j), i = 1,…, k, and {α(i_k+1),…, α(i_m) } ∩ {β(i_k+1),…, β(i_m) } = ?. A new bound for |detA[α|β ]| is obtained in terms of the eigenvalues of A when 2m = n and |α∩β| = 0.Let $\text{U}$_n be the group of n × n unitary matrices. Define the nonnegative number

where | α ∩ β| = k. It is proved that

Let A be semidefinite hermitian. We conjecture that ρ₀(A) ? ρ₁(A) ? ··· ? ρ_m(A). These inequalities have been tested by machine calculations.     

Permutation-operator inequalities on certain symmetry classes of tensors

If A∈T(m, N), the real-valued N-linear functions on E_m, and σ∈S_N, the symmetric group on {…,N}, then we define the permutation operator P_σ: T(m, N) → T(m, N) such that P_σ(A)(x₁,x₂,…,x_N = A(x_σ(1),x_σ(2),…, x_σ(N)). Suppose Σ^q_i=1n_i = N, where the n_i are positive integers. In this paper we present a condition on σ that is sufficient to guarantee that 〈P_σ(A₁?A₂???A_q),A₁?A₂?? ? A_q〉 ? 0 for A_i∈S(m, n_i), where S(m, n_i) denotes the subspace of T(m, n_i) consisting of all the fully symmetric members of T(m, n_i). Also we present a broad generalization of the Neuberger identity which is sometimes useful in answering questions of the type described below. Suppose G and H are subgroups of S_N. We let T_G(m, N) denote all A∈T(m, N) such that P_σ(A) = A for all σ∈G. We define the symmetrizer $\text{S}$_G: T(m, N)→T_G(m,N) such that $\text{S}{}_{\mathrm{G}}\text{(A) = 1/|G|Σ}{}_{\mathrm{\sigma \in G}}\text{P}{}_{\mathrm{\sigma }}\text{(A)}$. Suppose H is a subgroup of G and A∈T_H(m, N). Clearly $\text{6}\text{S}{}_{\mathrm{<mtext>G</mtext>}}\text{6(A) 6? 6A6.}$ We are interested in the reverse type of comparison. In particular, if D is a suitably chosen subset of T_H(m,N), then can we explicitly present a constant C>0 such that $\text{6}\text{S}{}_{\mathrm{G}}\text{(A)6?C6A6}$ for all A∈D?     

On finite groups with a certain number of centralizers

LetG be a finite group and #Cent(G) denote the number of centralizers of its elements.G is calledn-centralizer if #Cent(G)=n, and primitiven-centralizer if #Cent(G)=#Cent(G/Z(G))=n. In this paper we investigate the structure of finite groups with at most 21 element centralizers. We prove that such a group is solvable and ifG is a finite group such thatG/Z(G)?A₅, then #Cent(G)=22 or 32. Moroever, we prove that A₅ is the only finite simple group with 22 centralizers. Therefore we obtain a characterization of A₅ in terms of the number of centralizers     

On finite groups with a sylowp-subgroup of type (m,n)

A finitep-groupP is of type (m, n) ifP has nilpotency classm-1,P/P'≌Z _p ⁿ ×Z _p ⁿ and all the lower central factorsK _i (P)/K _i+1 (P) are cyclic of orderp ⁿ . Our main result on finite groups with a Sylowp-subgroup of type (m, n) is (Theorem 4.1): Let G be a finite group with a Sylow p-subgroup P of type (m, n), n≧2 p≧3, m≧(n+5)(p?1)+1. For H≦G denote \(\bar H = HO_{p'} (G)/O_{p'} (G)\) . If O_p (G) is not cyclic and P'₁ ≠ 1, then \(\bar P \Delta \bar G\) and \(\bar G = \bar P \cdot \bar T\) is a semidirect product of \(\bar P\) and \(\bar T\) , where \(\bar T\) is cyclic of order t, t|p-1. Here P₁ is the subgroup defined in section 0. This theorem easily yields that under its assumptionsN _G (P)/O ^P (N _G (P))≌G/O ^P (G), it gives information on the conjugacy pattern ofp-elements ofG and gives information on the structure ofp-local subgroups ofG (Theorems 4.2, 4.3 and 4.4).     

Generalized n-tuple colorings of a graph: A counterexample to a conjecture of Brigham and Dutton

In their papers (Technical Report CS-TR 50, University of Central Florida, 1980; J. Combin. Theory Ser. B32 (1982), 90–94) Brigham and Dutton introduce the notion of (n : i)-chromatic numbers of a graph, a generalization of Stahl's nth chromatic numbers (J. Combin. Theory Ser. B20, (1976), 185–203). The (n : i)-chromatic number of a graph G, denoted by χ_nⁱ(G), is the smallest integer m such that each vertex of G can be colored with a set of n colors in {1, 2,…, m} in such a way that any two adjacent vertices have exactly i colors in common. Brigham and Dutton conjecture at the end of loc cit that for all integers n and i with 0 ≤ i ≤ n ? 1, and for every graph G, χ_nⁱ⁺¹(G) ≤ χ_nⁱ(G). We prove this conjecture in some special cases and disprove it in the general case.     

On Thompson’s conjecture for alternating and symmetric groups of degree greater than 1361

Let G be a finite group G, and let N(G) be the set of sizes of its conjugacy classes. It is shown that, if N(G) equals N(Alt _n ) or N(Sym _n ), where n > 1361, then G has a composition factor isomorphic to an alternating group Altm with m ≤ n and the interval (m, n] contains no primes.     

A New Construction for Cohen–Macaulay Graphs

Let G be a finite simple graph on a vertex set V(G) = {x ₁₁,…, x _n1}. Also let m ₁,…, m _n  ≥ 2 be integers and G ₁,…, G _n be connected simple graphs on the vertex sets V(G _i ) = {x _i1,…, x _{im i} }. In this article, we provide necessary and sufficient conditions on G ₁,…, G _n for which the graph obtained by attaching the G _i to G is unmixed or vertex decomposable. Then we characterize Cohen–Macaulay and sequentially Cohen–Macaulay graphs obtained by attaching the cycle graphs or connected chordal graphs to arbitrary graphs.     

On a class of relatively prime sequences

For each natural number n, let a₀(n) = n, and if a₀(n),…,a_i(n) have already been defined, let a_i+1(n) > a_i(n) be minimal with (a_i+1(n), a₀(n) … a_i(n)) = 1. Let g(n) be the largest a_i(n) not a prime or the square of a prime. We show that g(n) ～ n and that $\text{g(n) > n + cn}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{log}\text{(n)}$ for some c > 0. The true order of magnitude of g(n) ? n seems to be connected with the fine distribution of prime numbers. We also show that “most” a_i(n) that are not primes or squares of primes are products of two distinct primes. A result of independent interest comes of one of our proofs: For every sufficiently large n there is a prime $\text{p < n}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$ with [$\text{n}\text{p}$] composite.     

Partition theorems for Abelian groups

Let A be a finite matrix with integral entries and G be an Abelian group. Define A to be partition regular in G if for every partition of G/(0) into finitely many classes there exist elemens x₁,…,x_m contained in one class such that A(x₁,…,x_m)^T = 0. Theorem. A is partition regular in G iff at least one of the following statements holds. (i) There is x ∈ G/(0) such that A(x,…,x)^T = 0. (ii) A is partition regular in Z_p^?₀ (p prime) and Z_p^?₀ ? G. (iii) A is partition regular in Z and the set of orders of elements in G is unbounded.     

Amalgamations of almost regular edge-colourings of simple graphs

A finite graph F is a detachment of a finite graph G if G can be obtained from F by partitioning V(F) into disjoint sets S₁, …, S_n and identifying the vertices in S_i to form a single vertex α_i for i = 1, …, n. Thus E(F) = E(G) and an edge which joins an element of S_i to an element of S_j in F will join α_i to α_j in G. If L is a subset of E(G) then G(L) denotes the subgraph of G such that V(G(L)) = V(G), E(G(L)) = L. We call a graph almost regular if there is an integer d such that every vertex has valency d or d + 1. Suppose that E(G) is partitioned into disjoint sets E₁, …, E_r. Hilton [3] found necessary and sufficient conditions for the existence of a detachment F of G such that F is a complete graph with 2r + 1 vertices and F(E_i) is a Hamilton circuit of F for i = 1, …, r. We give a new proof of Hilton's theorem, which also yields a generalisation. Specifically, for any q ∈ {0, 1, …, r}, we find necessary and sufficient conditions for G to have a detachment F without loops or multiple edges such that F(E₁), …, F(E_r) are almost regular and F(E₁), …, F(E_q) are 2-edge-connected and each vertex ξ of G arises by identification from a prescribed number g(ξ) of vertices of F.