A characterization of permutations via skew-hooks

A characterization of permutations is given using skew-hooks, such that the r-descents of the permutation are reflected in the structure of the skew-hook. The characterization yields a combinatorial proof of Foulkes' skew-hook rule for computing Eulerian numbers.     

On diagonal products of doubly stochastic matrices

The following result is proved: If A and B are distinct n × n doubly stochastic matrices, then there exists a permutation σ of {1, 2,…, n} such that ∏_ia_iσ(i) > ∏_ib_iσ(i).     

On arithmetic and asymptotic properties of up-down numbers

Let σ=(σ₁,…,σ_N), where σ_i=±1, and let C(σ) denote the number of permutations π of 1,2,…,N+1, whose up-down signature sign(π(i+1)-π(i))=σ_i, for i=1,…,N. We prove that the set of all up-down numbers C(σ) can be expressed by a single universal polynomial Φ, whose coefficients are products of numbers from the Taylor series of the hyperbolic tangent function. We prove that Φ is a modified exponential, and deduce some remarkable congruence properties for the set of all numbers C(σ), for fixed N. We prove a concise upper bound for C(σ), which describes the asymptotic behaviour of the up-down function C(σ) in the limit C(σ)?(N+1)!.     

Characterization of quadratic and cubic σ-polynomials

Here quadratic and cubic σ-polynomials are characterized, or, equivalently, chromatic polynomials of the graphs of order p, whose chromatic number is p ? 2 or p ? 3, are characterized. Also Robert Korfhage's conjecture that if σ² + bσ + a is a σ-polynomial then $\text{a ≤}\text{1}\text{2}\text{(b}{}^2\text{? 5b + 12)}$ is verified. In general, if σ(G) = Σ₀ⁿa_iσⁱ is a σ-polynomial of a graph G, then a_n?2 is determined.     

On interpolation of interpolating sequences

Let A be a uniform algebra on the compact space X and σ a probability measure on X. We define the Hardy spaces H^P(σ) and the H^P(σ) interpolating sequences S in the p-spectrum M_p of σ. Under some structural hypotheses on (A, σ), we prove that if a sequence S ⊂ M_p is H^P(σ) interpolating, then it is H^s(σ) interpolating for s < p. In the special case of the unit ball B of ?ⁿ this answers a natural question asked in [8].     

APPLICATIONS OF CLIFFORD ALGEBRAS TO INVOLUTIONS AND QUADRATIC FORMS

ABSTRACT

Let k be a field, char k ≠ 2, F = k(x), D a biquaternion division algebra over k, and σ an orthogonal involution on D with nontrivial discriminant. We show that there exists a quadratic form ? ∈ I ²(F) such that dim ? = 8, [C(?)] = [D], and ? does not decompose into a direct sum of two forms similar to two-fold Pfister forms. This implies in particular that the field extension F(D)/F is not excellent. Also we prove that if A is a central simple K-algebra of degree 8 with an orthogonal involution σ, then σ is hyperbolic if and only if σ _K(A) is hyperbolic. Finally, let σ be a decomposable orthogonal involution on the algebra M _{2 ^m} (K). In the case m ≤ 5 we give another proof of the fact that σ is a Pfister involution. If m ≥ 2 ^n?2 ? 2 and n ≥ 5, we show that q _σ ∈ I ⁿ (K), where q _σ is a quadratic form corresponding to σ. The last statement is founded on a deep result of Orlov et al. (2000) concerning generic splittings of quadratic forms.     

Functions, Measures, and Equipartitioning Convex k-Fans

A k-fan in the plane is a point x∈?² and k halflines starting from x. There are k angular sectors σ ₁,…,σ _k between consecutive halflines. The k-fan is convex if every sector is convex. A (nice) probability measure μ is equipartitioned by the k-fan if μ(σ _i )=1/k for every sector. One of our results: Given a nice probability measure μ and a continuous function f defined on sectors, there is a convex 5-fan equipartitioning μ with f(σ ₁)=f(σ ₂)=f(σ ₃).     

Permanents of d-dimensional matrices

Let A = (A_i1i2…_id) be an n₁ × n₂ × · × n_d matrix over a commutative ring. The permanent of A is defined by per (A) = ∑πⁿ_1i = ₁A_iσ2(_i)σ₃(_i)…σ_d(_i), where the summation ranges over all one-to-one functions σ_k from {1,2,…, n₁} to {1,2,…, n_k}, k = 2,3,…, d. In this paper it is shown that a number of properties of permanents of 2-dimensional matrices extend to higher-dimensional matrices. In particular, permanents of nonnegative d-dimensional matrices with constant hyperplane sums are investigated. The paper concludes by introducing s-permanents, which generalize the definition above that the permanent becomes the 1-permanent, and showing that an s-permanent can always be converted into a 1-permanent.     

Recurrence Formulas for Kostka and Inverse Kostka Numbers via Quantum Cohomology of Grassmannians

A Gröbner basis for the small quantum cohomology of Grassmannian G _k,n is constructed and used to obtain new recurrence relations for Kostka numbers and inverse Kostka numbers. Using these relations it is shown how to determine inverse Kostka numbers which are related to the mod-p Wu formula.     

A Description of an algebraic automorphism in terms of the radical of its minimal polynomial

It is shown in [5, Theorem 3] that if s is an algebraic automorphism of a k-vector space V with minimalpolynomial μ(T) ∈ K[T], then the extension σ of s to a k-automorphism of the field of quotients of the symmetric k-algebra k(V) of V is completely determined by μ(T) (and dim_kV). In Theorem 4 of this article, we show that σ is almost completely determined by the radical μ₀(T) of μ(T) and we see in particular that if μ(T) is separable then the rationality of (the fixed field of) σ depends only on μ₀(T). In Theorem 5, the rationality of σ is established under certain assumptions on the Galois group of μ₀(T).     

Central and local limit theorems applied to asymptotic enumeration

Let a double sequence a_n(k) ? 0 be given. We prove a simple theorem on generating functions which can be used to establish the asymptotic normality of a_n(k) as a function of k. Next we turn our attention to local limit theorems in order to obtain asymptotic formulas for a_n(k). Applications include constant coefficient recursions, Stirling numbers, and Eulerian numbers.     

Spectral representations for abelian automorphism groups of von Neumann algebras

Let $\text{A}$ be a von Neumann algebra, let σ be a strongly continuous representation of the locally compact abelian group G as ¹-automorphisms of $\text{A}$. Let M(σ) be the Banach algebra of bounded linear operators on $\text{A}$ generated by ∝ σ_tdμ(t) (μ?M(G)). Then it is shown that M(σ) is semisimple whenever either (i) $\text{A}$ has a σ-invariant faithful, normal, semifinite, weight (ii) σ is an inner representation or (iii) G is discrete and each σ_t is inner. It is shown that the Banach algebra L(σ) generated by $\text{∝ ?(t)σ}{}_{\mathrm{t}}\text{dt (? ? L}{}^1\text{(G))}$ is semisimple if a is an integrable representation. Furthermore, if σ is an inner representation with compact spectrum, it is shown that L(σ) is embedded in a commutative, semisimple, regular Banach algebra with isometric involution that is generated by projections. This algebra is contained in the ultraweakly continuous linear operators on $\text{A}$. Also the spectral subspaces of σ are given in terms of projections.     

Small cycles and 2-factor passing through any given vertices in graphs

The theory of vertex-disjoint cycles and 2-factor of graphs has important applications in computer science and network communication. For a graph G, let σ ₂(G):=min?{d(u)+d(v)|uv ? E(G),u≠v}. In the paper, the main results of this paper are as follows:

1. Let k≥2 be an integer and G be a graph of order n≥3k, if σ ₂(G)≥n+2k?2, then for any set of k distinct vertices v ₁,…,v _k , G has k vertex-disjoint cycles C ₁,C ₂,…,C _k of length at most four such that v _i ∈V(C _i ) for all 1≤i≤k.
2. Let k≥1 be an integer and G be a graph of order n≥3k, if σ ₂(G)≥n+2k?2, then for any set of k distinct vertices v ₁,…,v _k , G has k vertex-disjoint cycles C ₁,C ₂,…,C _k such that:
   1. v _i ∈V(C _i ) for all 1≤i≤k.
   2. V(C ₁)∪???∪V(C _k )=V(G), and
   3. |C _i |≤4, 1≤i≤k?1.

Moreover, the condition on σ ₂(G)≥n+2k?2 is sharp.     

Enumeration of finite topologies

Let T₀(n) be the number of marked topologies satisfying the separation axiom T₀ that can be imposed on a finite set of n elements. In this paper the formula $$T_0 \left( n \right) = \Sigma \frac{{n!}}{{p_1 !...p_m !}}V\left( {p_1 , ..., p_m } \right)$$ is obtained, where the summation extends over all ordered sets of natural numbers (p₁, ..., p_m) such that p₁+...+p_m=n, and V(p₁, ..., p_m) denotes the number of matrices σ=(σ_ij) of ordern with the following properties: 1) each of the entries σ_ij is either 0 or 1, and if σ_ij=1 andσ_ij=1, then σ_ij=1;2) if the matrix σ is partitioned into blocks of sizes p_ixp_j, then all blocks under the main diagonal are zero, all diagonal blocks are identity matrices, and in each column of any block situated above the main diagonal at least one entry is 1. Some properties of the values V(p₁, ..., p_m)are obtained; in particular, it is shown that all these values are odd. Formulas are obtained for V(P₁, ..., p_m) corresponding to the simplest sets (p₁, ..., P_m) needed to calculate T₀(n) for n?8 (without using a computer).     

A Tauberian theorem related to Weyl's criterion

Let {x_n} be a sequence of real numbers and let a(n) be a sequence of positive real numbers, with A(N) = Σ_n=1^Na(n). Tsuji has defined a notion of a(n)-uniform distribution mod 1 which is related to the problem of determining those real numbers t₀ for which A(N)^?1 Σ_n=1^Na(n)e^?it₀x_n → 0 as N → ∞. In case f(s) = Σ_n=1^∞a(n)e^?sx_n, s = σ + it, is analytic in the right half-plane 0 < σ, and satisfies a certain smoothness condition as σ → 0 +, we show that f(σ)^?1f(σ + it₀) → 0 as σ → 0 + if and only if A(N)^?1 Σ_n=1^Na(n)e^?it₀x_n → 0 as N → ∞.     

Almost continuity on generalized topological spaces

For any unbounded sequence {n _k } of positive real numbers, there exists a permutation {n _σ(k)} such that the discrepancies of {n _σ(k) x} obey the law of the iterated logarithm exactly in the same way as the uniform i.i.d. sequence {U _k }.     

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?     

Numerical solution of parameter‐dependent linear systems

We are interested in the numerical solution of the complex large linear system, (σ²A+σB+C)x=f(σ), for many, possibly a few hundreds, values of the complex parameter σ in a wide range. We assume that A, B and C are large, sparse, symmetric matrices, as is the case in several application problems. In particular, we focus on the following structured right‐hand side, f(σ)=FΦ(σ), where F is a (tall) rectangular matrix whose entries are independent of σ. We propose to approximate the solution x=x(σ) by means of a projection onto a single vector subspace, and a subsequent solution of the reduced dimension problem, for all values of interest of the parameter σ. Numerical experiments report the effectiveness of our approach on real application problems. Copyright © 2005 John Wiley & Sons, Ltd.     

Author index

A matrix T=(t_ik) is introduced, the coefficients of which are defined by $\text{k}{}_{\mathrm{ik}}\text{:= (}\text{i}{}^{\mathrm{k}}\text{(ik)!)}\text{Σ}{}_{\mathrm{x?S}}{}_{\mathrm{n}}\text{a}{}_{\mathrm{i}}\text{(x)}{}^{\mathrm{k}}\text{, i, k?N={1, 2, 3,…,}}$, where a_i(x) denotes the s the number of i cycles in the element x of the symmetric group S_n. It is shown that these numbers are natural numbers, that they are easy to evaluate, and that they serve very well in order to formulate an infinite number of characterizations of multiply transitive subgroups of symmetric groups in terms of the cycle structure of their elements.     

Hardy’s theorem for zeta-functions of quadratic forms

LetQ(u ₁,…,u ₁) =Σd _ij u _i u _j (i,j = 1 tol) be a positive definite quadratic form inl(≥3) variables with integer coefficientsd _ij (=d _ji ). Puts=σ+it and for σ>(l/2) write $$Z_Q (s) = \Sigma '(Q(u_1 ,...,u_l ))^{ - s} ,$$ where the accent indicates that the sum is over alll-tuples of integer (u ₁,…,u _l ) with the exception of (0,…, 0). It is well-known that this series converges for σ>(l/2) and that (s-(l/2))Z _Q (s) can be continued to an entire function ofs. Let σ be any constant with 0<σ<1/100. Then it is proved thatZ _Q (s)has ?_δTlogT zeros in the rectangle(|σ-1/2|≤δ, T≤t≤2T).