Schur functions and the invariant polynomials characterizing U(n) tensor operators

We give a direct formulation of the invariant polynomials _μG_q⁽ⁿ⁾(, Δ_i,;, x_{i,i + 1},) characterizing U(n) tensor operators p, q, …, q, 0, …, 0 in terms of the symmetric functions S_λ known as Schur functions. To this end, we show after the change of variables Δ_i = γ_i − δ_i and x_{i, i + 1} = δ_i − δ_{i + 1} that_μG_q⁽ⁿ⁾(,Δ_i;, x_{i, i + 1},) becomes an integral linear combination of products of Schur functions S_α(, γ_i,) · S_β(, δ_i,) in the variables {γ₁,…, γ_n} and {δ₁,…, δ_n}, respectively. That is, we give a direct proof that _μG_q⁽ⁿ⁾(,Δ_i,;, x_{i, i + 1},) is a bisymmetric polynomial with integer coefficients in the variables {γ₁,…, γ_n} and {δ₁,…, δ_n}. By making further use of basic properties of Schur functions such as the Littlewood-Richardson rule, we prove several remarkable new symmetries for the yet more general bisymmetric polynomials _μ^mG_q⁽ⁿ⁾(γ₁,…, γ_n; δ₁,…, δ_m). These new symmetries enable us to give an explicit formula for both _μ^mG₁⁽ⁿ⁾(γ; δ) and ₁G₂⁽ⁿ⁾(γ; δ). In addition, we describe both algebraic and numerical integration methods for deriving general polynomial formulas for _μ^mG_q⁽ⁿ⁾(γ; δ).     

Representations for the first associated q-classical orthogonal polynomials

Let {p_k(x; q)} be any system of the q-classical orthogonal polynomials, and let be the corresponding weight function, satisfying the q-difference equation D_q(σ)=τ, where σ and τ are polynomials of degree at most 2 and exactly 1, respectively. Further, let {p_k⁽¹⁾(x;q)} be associated polynomials of the polynomials {p_k(x; q)}. Explicit forms of the coefficients b_n,k and c_n,k in the expansions

are given in terms of basic hypergeometric functions. Here _k(x) equals x^k if σ⁺(0)=0, or (x;q)_k if σ⁺(1)=0, where σ⁺(x)σ(x)+(q−1)xτ(x). The most important representatives of those two classes are the families of little q-Jacobi and big q-Jacobi polynomials, respectively.Writing the second-order nonhomogeneous q-difference equation satisfied by p_n−1⁽¹⁾(x;q) in a special form, recurrence relations (in k) for b_n,k and c_n,k are obtained in terms of σ and τ.     

q-Bernstein polynomials and their iterates

Let B_n( f,q;x), n=1,2,… be q-Bernstein polynomials of a function f : [0,1]→C. The polynomials B_n( f,1;x) are classical Bernstein polynomials. For q≠1 the properties of q-Bernstein polynomials differ essentially from those in the classical case. This paper deals with approximating properties of q-Bernstein polynomials in the case q>1 with respect to both n and q. Some estimates on the rate of convergence are given. In particular, it is proved that for a function f analytic in {z: |z|<q+} the rate of convergence of {B_n( f,q;x)} to f(x) in the norm of C[0,1] has the order q⁻ⁿ (versus 1/n for the classical Bernstein polynomials). Also iterates of q-Bernstein polynomials {B_n^j_n( f,q;x)}, where both n→∞ and j_n→∞, are studied. It is shown that for q(0,1) the asymptotic behavior of such iterates is quite different from the classical case. In particular, the limit does not depend on the rate of j_n→∞.     

A continuous function space with a Faber basis

Let be compact with #S=∞ and let C(S) be the set of all real continuous functions on S. We ask for an algebraic polynomial sequence (P_n)_n=0^∞ with deg P_n=n such that every fC(S) has a unique representation f=∑_i=0^∞ α_iP_i and call such a basis Faber basis. In the special case of , 0<q<1, we prove the existence of such a basis. A special orthonormal Faber basis is given by the so-called little q-Legendre polynomials. Moreover, these polynomials state an example with A(S_q)≠U(S_q)=C(S_q), where A(S_q) is the so-called Wiener algebra and U(S_q) is the set of all fC(S_q) which are uniquely represented by its Fourier series.     

Generalized Bernstein Polynomials

We introduce polynomials B ⁿ _i (x;ω|q), depending on two parameters q and ω, which generalize classical Bernstein polynomials, discrete Bernstein polynomials defined by Sablonnière, as well as q-Bernstein polynomials introduced by Phillips. Basic properties of the new polynomials are given. Also, formulas relating B ⁿ _i (x;ω|q), big q-Jacobi and q-Hahn (or dual q-Hahn) polynomials are presented. This revised version was published online in July 2006 with corrections to the Cover Date.     

Minimum degree conditions for -linked graphs

For a fixed multigraph H with vertices w₁,…,w_m, a graph G is H-linked if for every choice of vertices v₁,…,v_m in G, there exists a subdivision of H in G such that v_i is the branch vertex representing w_i (for all i). This generalizes the notions of k-linked, k-connected, and k-ordered graphs.Given a connected multigraph H with k edges and minimum degree at least two and n7.5k, we determine the least integer d such that every n-vertex simple graph with minimum degree at least d is H-linked. This value D(H,n) appears to equal the least integer d^′ such that every n-vertex graph with minimum degree at least d^′ is b(H)-connected, where b(H) is the maximum number of edges in a bipartite subgraph of H.     

On the multiplicity of the eigenvalues of a graph

Given a graph G with characteristic polynomial ϕ(t), we consider the ML-decomposition ϕ(t) = q ₁(t)q ₂(t)² ... q _m (t)^m, where each q _i (t) is an integral polynomial and the roots of ϕ(t) with multiplicity j are exactly the roots of q _j (t). We give an algorithm to construct the polynomials q _i (t) and describe some relations of their coefficients with other combinatorial invariants of G. In particular, we get new bounds for the energy E(G) = |λ_i| of G, where λ₁, λ₂, ..., λ_n are the eigenvalues of G (with multiplicity). Most of the results are proved for the more general situation of a Hermitian matrix whose characteristic polynomial has integral coefficients. This work was done during a visit of the second named author to UNAM.     

Lower bounds for the cardinality of minimal blocking sets in projective spaces

In this paper new lower bounds for the cardinality of minimal m-blocking sets are determined. Let r₂(q) be the number such that q+r₂(q)+1 is the cardinality of the smallest non-trivial line-blocking set in a plane of order q. If B is a minimal m-blocking set in PG(n,q) that contains at most q^m+q^m−1+…+q+1+r₂(q)·(∑_i=2m−n′^m−1qⁱ) points for an integer n′ satisfying mn′2m, then the dimension of B is at most n′. If the dimension of B is n′, then the following holds. The cardinality of B equals q^m+q^m−1+…+q+1+r₂(q)(∑_i=2m−n′^m−1qⁱ). For n′=m the set B is an m-dimensional subspace and for n′=m+1 the set B is a cone with an (m−2)-dimensional vertex over a non-trivial line-blocking set of cardinality q+r₂(q)+1 in a plane skew to the vertex. This result is due to Heim (Mitt. Math. Semin. Giessen 226 (1996), 4–82). For n′>m+1 and q not a prime the number q is a square and for q16 the set B is a Baer cone. If q is odd and |B|<q^m+q^m−1+…+q+1+r₂(q)(q^m−1+q^m−2), it follows from this result that the subspace generated by B has dimension at most m+1. Furthermore we prove that in this case, if , then B is an m-dimensional subspace or a cone with an (m−2)-dimensional vertex over a non-trivial line-blocking set of cardinality q+r₂(q)+1 in a plane skew to the vertex. For q=p^3h, p7 and q not a square we show this assertion for |B|q^m+q^m−1+…+q+1+q^2/3·(q^m−1+…+1).     

On the number of queries necessary to identify a permutation

Let p and q be two permutations over {1, 2,…, n}. We denote by m(p, q) the number of integers i, 1 ≤ i ≤ n, such that p(i) = q(i). For each fixed permutation p, a query is a permutation q of the same size and the answer a(q) to this query is m(p, q). We investigate the problem of finding the minimum number of queries required to identify an unknown permutation p. A polynomial-time algorithm that identifies a permutation of size n by O(n · log₂n) queries is presented. The lower bound of this problem is also considered. It is proved that the problem of determining the size of the search space created by a given set of queries and answers is #P-complete. Since this counting problem is essential for the analysis of the lower bound, a complete analysis of the lower bound appears infeasible. We conjecture, based on some preliminary analysis, that the lower bound is Ω(n · log₂n).     

The asymptotic number of labeled connected graphs with a given number of vertices and edges

Let c(n, q) be the number of connected labeled graphs with n vertices and q ≤ N = (2n ) edges. Let x = q/n and k = q ? n. We determine functions w_k ? 1. a(x) and φ(x) such that c(n, q) ? w_k(q^N)eⁿφ(x)+a(x) uniformly for all n and q ≥ n. If ? > 0 is fixed, n→ ∞ and 4q > (1 + ?)n log n, this formula simplifies to c(n, q) ? (N^q) exp(–ne^?2q/n). on the other hand, if k = o(n^1/2), this formula simplifies to c(n, n + k) ? 1/2 w_k (3/π)^1/2 (e/12k)^k/2nⁿ?^(3k?1)/2.     

Convexity preserving and predicting by Bernstein polynomials

It is known that the Bernstein polynomials of a function f defined on [0, 1 ] preserve its convexity properties, i.e., if f⁽ⁿ⁾ 0 then for m n, (B_mf)⁽ⁿ⁾ 0. Moreover, if f is n-convex then (B_mf)⁽ⁿ⁾ 0. While the converse is not true, we show that if f is bounded on (a, b) and if for every subinterval [α, β] (a, b) the nth derivative of the mth Bernstein polynomial of f on [α, β] is nonnegative then f is n-convex.     

Two New Classes of Difference Families

A Z-cyclic triplewhist tournament for 4n+1 players, or briefly a TWh(4n+1), is equivalent to a n-set {(a_i, b_i, c_i, d_i) | i=1, …, n} of quadruples partitioning Z_4n+1−{0} with the property that ⁿ_i=1 {±(a_i−c_i), ±(b_i−d_i)}=ⁿ_i=1 {±(a_i−b_i), ±(c_i−d_i)}=ⁿ_i=1 {±(a_i−d_i), ±(b_i−c_i)}=Z_4n+1−{0}. The existence problem for Z-cyclic TWh(p)'s with p a prime has been solved for p1 (mod 16). I. Anderson et al. (1995, Discrete Math.138, 31–41) treated the case of p≡5 (mod 8) while Y. S. Liaw (1996, J. Combin. Des.4, 219–233) and G. McNay (1996, Utilitas Math.49, 191–201) treated the case of p≡9 (mod 16). In this paper, besides giving easier proofs of these authors' results, we solve the problem also for primes p≡1 (mod 16). The final result is the existence of a Z-cyclic TWh(v) for any v whose prime factors are all≡1 (mod 4) and distinct from 5, 13, and 17.     

An umbral calculus for polynomials characterizing U(n) tensor operators

After the change of variables Δ_i = γ_i ? δ_i and x_{i,i + 1} = δ_i ? δ_{i + 1} we show that the invariant polynomials _μG⁽ⁿ⁾_q(, Δ_i, ; , x_i,i+1,) characterizing U(n) tensor operators 〈p, q,…, q, 0,…, 0〉 become an integral linear combination of Schur functions S_λ(γ ? δ) in the symbol γ ? δ, where γ ? δ denotes the difference of the two sets of variables {γ₁ ,…, γ_n} and {δ₁ ,…, δ_n}. We obtain a similar result for the yet more general bisymmetric polynomials ^m_μG⁽ⁿ⁾_q(γ₁ ,…, γ_n; δ₁ ,…, δ_m). Making use of properties of skew Schur functions $\text{S}{}_{\mathrm{<mtext>\lambda </mtext><mtext>\rho </mtext>}}$ and S_λ(γ ? δ) we put together an umbral calculus for ^m_μG⁽ⁿ⁾_q(γ; δ). That is, working entirely with polynomials, we uniquely determine ^m_μG⁽ⁿ⁾_q(γ; δ) from ^m_μG⁽ⁿ⁾_{q ? 1}(γ; δ) and combinatorial rules involving Ferrers diagrams (i.e., partitions), provided that n ≥ (μ + 1)q. (This restriction does not interfere with writing the general case of ^m_μG⁽ⁿ⁾_q(γ; δ) as a linear combination of S_λ(γ ? δ).) As an application we deduce “conjugation” symmetry for ⁿ_μG⁽ⁿ⁾_q(γ; δ) from “transposition” symmetry by showing that these two symmetries are equivalent.     

The Asymptotic Distribution of Singular-Values with Applications to Canonical Correlations and Correspondence Analysis

Let X_n, n = 1, 2, ... be a sequence of p × q random matrices, p ≥ q. Assume that for a fixed p × q matrix B and a sequence of constants b_n → ∞, the random matrix b_n(X_n − B) converges in distribution to Z. Let ψ(X_n) denote the q-vector of singular values of X_n. Under these assumptions, the limiting distribution of b_n (ψ(X_n) − ψ(B)) is characterized as a function of B and of the limit matrix Z. Applications to canonical correlations and to correspondence analysis are given.     

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.     

Error bounds for least squares approximation by polynomials

Let f ε Cⁿ⁺¹[−1, 1] and let H[f](x) be the nth degree weighted least squares polynomial approximation to f with respect to the orthonormal polynomials q_k associated with a distribution dα on [−1, 1]. It is shown that if q_n+1/q_n max(q_n+1(1)/q_n(1), −q_n+1(−1)/q_n(−1)), then f − H[f] f^{n + 1} · q_n+1/q_{n + 1}^{(n + 1)}, where · denotes the supremum norm. Furthermore, it is shown that in the case of Jacobi polynomials with distribution (1 − t)^α (1 + t)^β dt, α, β > −1, the condition on q_n+1/q_n is satisfied when either max(α,β) −1/2 or −1 < α = β < −1/2.     

Affine Hecke algebras and the Schubert calculus

Using a combinatorial approach that avoids geometry, this paper studies the structure of K_T(G/B), the T-equivariant K-theory of the generalized flag variety G/B. This ring has a natural basis (the double Grothendieck polynomials), where is the structure sheaf of the Schubert variety X_w. For rank two cases we compute the corresponding structure constants of the ring K_T(G/B) and, based on this data, make a positivity conjecture for general G which generalizes the theorems of M. Brion (for K(G/B)) and W. Graham (for H_T^*(G/B)). Let [X^λ]K_T(G/B) be the class of the homogeneous line bundle on G/B corresponding to the character of T indexed by λ. For general G we prove “Pieri–Chevalley formulas” for the products , , , and , where λ is dominant. By using the Chern character and comparing lowest degree terms the products which are computed in this paper also give results for the Grothendieck polynomials, double Schubert polynomials, and ordinary Schubert polynomials in, respectively K(G/B), H_T^*(G/B) and H^*(G/B).     

Toughness and longest cycles in 2-connected planar graphs

Let G be a planar graph on n vertices, let c(G) denote the length of a longest cycle of G, and let w(G) denote the number of components of G. By a well-known theorem of Tutte, c(G) = n (i.e., G is hamiltonian) if G is 4-connected. Recently, Jackson and Wormald showed that c(G) ≥ βn^α for some positive constants β and α ≅ 0.2 if G is 3-connected. Now let G have connectivity 2. Then c(G) may be as small as 4, as with K_2,n-2, unless we bound w(G − S) for every subset S of V(G) with |S| = 2. Define ξ(G) as the maximum of w(G − S) taken over all 2-element subsets S ⊆ V(G). We give an asymptotically sharp lower bound for the toughness of G in terms of ξ(G), and we show that c(G) ≥ θ ln n for some positive constant θ depending only on ξ(G). In the proof we use a recent result of Gao and Yu improving Jackson and Wormald's result. Examples show that the lower bound on c(G) is essentially best-possible. © 1996 John Wiley & Sons, Inc.     

On B(n,k) 2-groups

A finite group G is said to be a B(n, k) group if for any n-element subset {a ₁,…, a _n } of G, |{a _i a _j |1 ≤ i, j ≤ n}| ≤k. In this article, we give characterizations of the B(5, 19) 2-groups, and the B(6, k) 2-groups for 21 ≤ k ≤ 28.     

U(n) Wigner coefficients,the path sum formula,and invariant G-functions

We prove the path sum formula for computing the U(n) invariant denominator functions associated to stretched U(n) Wigner operators. A family of U(n) invariant polynomials G_[λ]⁽ⁿ⁾ is then defined which generalize the _μG_q⁽ⁿ⁾ polynomials previously studied. The G_[λ]⁽ⁿ⁾ polynomials are shown to satisfy a number of difference equations and have symmetry properties similar to the _μG_q⁽ⁿ⁾ polynomials. We also give a direct proof of the important transposition symmetry for the G_[λ]⁽ⁿ⁾ polynomials. To enable the non-specialist to understand the foundations for these remarkable polynomials, we provide an exposition of the boson calculus and the construction of the multiplicity-free U(n) Wigner operators.