A combinatorial interpretation of the inverse kostka matrix

The Kostka matrix K relates the. homogeneous and the Schur bases in the ring of symmetric functions where K _λ,μenumerates the number of column strict tableaux of shape λ and type μ. We make use of the Jacobi -Trudi identity to give a combinatorial interpretation for the inverse of the Kostka matrix in terms of certain types of signed rim hook tabloids. Using this interpretation, the matrix identity KK ^?1=Iis given a purely combinatorial proof. The generalized Jacobi-Trudi identity itself is also shown to admit a combinatorial proof via these rim hook tabloids. A further application of our combinatorial interpretation is a simple rule for the evaluation of a specialization of skew Schur functions that arises in the computation of plethysms.     

A combinatorial rule for the schur function expansion of the Plethysm S(1a,b)[Pk]

We present a simple combinatorial rule to expand the plethysm P_n[S(1^a,b)](x) of a power summetric function P_n(x) and a Schur function of hook shapeS(1^a,b)(x), as a sum of Schur functions. The key ingredient of our proof is a correspondence between the circle diagrams, introduced by Chen, Garsia and Remmel [6] in their SXP algorithm to compute the Schur function expansion of P_n[S_λ], and certain special rim hook and transposed special rim hook tabloids which is of interest in its own right. As an application of our rule, we drive explicit formulas for the coefficient of any Schur function of hook shape in the Schur function expansion of a plethysm of any two Schur functions of hook shape.     

The Flagged Cauchy Determinant

We consider a flagged form of the Cauchy determinant, for which we provide a combinatorial interpretation in terms of nonintersecting lattice paths. In combination with the standard determinant for the enumeration of nonintersecting lattice paths, we are able to give a new proof of the Cauchy identity for Schur functions. Moreover, by choosing different starting and end points for the lattice paths, we are led to a lattice path proof of an identity of Gessel which expresses a Cauchy-like sum of Schur functions in terms of the complete symmetric functions.     

A simple bound for the remainder of the neumann series in the case of a self-adjoint compact operator

We consider the functional equation of the second kind \gf − λK\gf = f with K a compact self-adjoint linear operator on a Hilbert space: a Fredholm integral equation of the second kind, for example. We establish the simple bound where λ is any regular value of K; ø is the solution of the equation corresponding to λ; λ₁ is the characteristic value of K smallest in absolute value; and N = 0, 1, 2, .... For \s|λ\s| < \s|λ₁\s|, this is an estimate for the remainder of the partial sums of the Neumann series.     

The Hoffman number of a graph

For a connected graph G with n vertices, let {λ₁,λ₂,…,λ_r} be the set of distinct positive eigenvalues of the Laplacian matrix of G. The Hoffman number μ(G) of G is defined by μ(G)=λ₁λ₂…λ_r/n. In this paper, we study some properties and applications of the Hoffman number.     

Multiplying Schur functions

A new combinatorial rule for expanding the product of Schur functions as a sum of Schur functions is formulated. The rule has several advantages over the Littlewood-Richardson rule (D. E. Littlewood and A. R. Richardson, Philos. Trans. Roy. Soc. London Ser. A233 (1934), 49–141). First this rule allows for direct computation of the expansion of the product of any number of Schur functions, not just the product of two Schur functions. Also, the rule is easily stated and is well suited to computer implementation. It is shown that the rule implies the Littlewood-Richardson rule and gives a combinatorial proof that the coefficient of S_λ in the product S_μS_ν equals the coefficient of S_ν in the expansion of the skew Schur function S_λ/μ. The rule is derived from some results proved independently by A. P. Hillman and R. M. Grassl (J. Combin. Comput. Sci. Systems5 (1980), 305–316) and by D. White (J. Combin. Theory Ser. A30 (1981), 237–247) on the Robinson-Schensted-Knuth correspondence.     

Bijective proofs of formulae for the number of standard Yound tableaux

We give a bijective proof of a formula due independently to Frobenius and Young for the number of standard Young tableau of shape λ for λ any partition. Frame, Robinson, and Thrall derived their hook formula for the number of standard Young tableau from the Frobenius-Young formula. As a corollary to our bijective proof of the Frobenius-Young formula, we also give a bijective proof of the Frame-Robinson-Thrall hook formula.     

Applications of the Frobenius Formulas for the Characters of the Symmetric Group and the Hecke Algebras of Type A

We give a simple combinatorial proof of Ram's rule for computing the characters of the Hecke Algebra. We also establish a relationship between the characters of the Hecke algebra and the Kronecker product of two irreducible representations of the Symmetric Group which allows us to give new combinatorial interpretations to the Kronecker product of two Schur functions evaluated at a Schur function of hook shape or a two row shape. We also give a formula for the regular representation of the Hecke algebra.     

On the efficiency of a testimator for the mean of an inverse Gaussian distribution

Though the sample mean is a natural estimator for the mean μ of an Inverse Gaussian (IG) distribution having another parameter λ, when a guess μ₀ for μ seems plausible, an alternative adaptive estimator which shrinks towards μ₀ when a preliminary test for H₀:μ = μ₀ is tenable or else towards , is considered a suitable competitor. Certain numerical illustrations are presented showing higher efficiency of such a testimator over in several situations when the sample size is small and λ is either known or unknown.     

Quasisymmetric Schur functions

We introduce a new basis for quasisymmetric functions, which arise from a specialization of nonsymmetric Macdonald polynomials to standard bases, also known as Demazure atoms. Our new basis is called the basis of quasisymmetric Schur functions, since the basis elements refine Schur functions in a natural way. We derive expansions for quasisymmetric Schur functions in terms of monomial and fundamental quasisymmetric functions, which give rise to quasisymmetric refinements of Kostka numbers and standard (reverse) tableaux. From here we derive a Pieri rule for quasisymmetric Schur functions that naturally refines the Pieri rule for Schur functions. After surveying combinatorial formulas for Macdonald polynomials, including an expansion of Macdonald polynomials into fundamental quasisymmetric functions, we show how some of our results can be extended to include the t parameter from Hall-Littlewood theory.     

Applications of minor summation formula III, Plücker relations, lattice paths and Pfaffian identities

The initial purpose of the present paper is to provide a combinatorial proof of the minor summation formula of Pfaffians in [Ishikawa, Wakayama, Minor summation formula of Pfaffians, Linear and Multilinear Algebra 39 (1995) 285-305] based on the lattice path method. The second aim is to study applications of the minor summation formula for obtaining several identities. Especially, a simple proof of Kawanaka's formula concerning a q-series identity involving the Schur functions [Kawanaka, A q-series identity involving Schur functions and related topics, Osaka J. Math. 36 (1999) 157-176] and of the identity in [Kawanaka, A q-Cauchy identity involving Schur functions and imprimitive complex reflection groups, Osaka J. Math. 38 (2001) 775-810] which is regarded as a determinant version of the previous one are given.     

Young-Fibonacci insertion, tableauhedron and Kostka numbers

This work is first concerned with some properties of the Young-Fibonacci insertion algorithm and its relation with Fomin's growth diagrams. It also investigates a relation between the combinatorics of Young-Fibonacci tableaux and the study of Okada's algebras associated to the Young-Fibonacci lattice. The original algorithm was introduced by Roby and we redefine it in such a way that both the insertion and recording tableaux of any permutation are conveniently interpreted as saturated chains in the Young-Fibonacci lattice. Using our conventions, we give a simpler proof of a property of Killpatrick's evacuation algorithm for Fibonacci tableaux. It also appears that this evacuation is no longer needed in making Roby's and Fomin's constructions coincide. We provide the set of Young-Fibonacci tableaux of size n with a structure of graded poset called tableauhedron, induced by the weak order of the symmetric group, and realized by transitive closure of elementary transformations on tableaux. We show that this poset gives a combinatorial interpretation of the coefficients of the transition matrix from the analogue of complete symmetric functions to analogue of the Schur functions in Okada's algebra associated to the Young-Fibonacci lattice. We prove a similar result relating usual Kostka numbers with four partial orders on Young tableaux, studied by Melnikov and Taskin.     

An algorithm for computing plethysm coefficients

The plethysm of two Schur functions can be expressed as a sum of Schur functions with nonnegative integer coefficients. Current algorithms for computing plethysms are designed to compute the whole expansion. However, in some applications only a few coefficients are of interest. In this work, we develop an algorithm for calculating individual plethysm coefficients. We also give a simple result concerning the zero coefficients which is obtained from the combinatorial properties of the Kostka and the inverse Kostka numbers.     

Spherical functions and immanants

Let λ be an irreducible character of S_n corresponding to the partition (r,s) of n. Let A be a positive semidefinite Hermitian n × n matrix. Let d_λ(A) and per(A) be the immanants corresponding to λ and to the trivial character of S_n, respectively. A proof of the inequality dλ(A)≤λ(id)per(A) is given.     

A Pieri rule for skew shapes

The Pieri rule expresses the product of a Schur function and a single row Schur function in terms of Schur functions. We extend the classical Pieri rule by expressing the product of a skew Schur function and a single row Schur function in terms of skew Schur functions. Like the classical rule, our rule involves simple additions of boxes to the original skew shape. Our proof is purely combinatorial and extends the combinatorial proof of the classical case.     

Decomposition of a rational matrix into partial fractions

In this paper a technique is developed for the expansion of a rational matrix F(λ)=G(λ)L^-1(λ)(orF(λ)=L^-1(λ)G(λ)into block partial fractions when the denominator has multiple roots. The method consists in the construction of interpolating matrix polynomials and their properties. Moreover, the approach is extended when L(λ) has nonlinear divisors.     

3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects

We present a new data structure for a set of n convex simply-shaped fat objects in the plane, and use it to obtain efficient and rather simple solutions to several problems including (i) vertical ray shooting—preprocess a set of n non-intersecting convex simply-shaped flat objects in 3-space, whose xy-projections are fat, for efficient vertical ray shooting queries, (ii) point enclosure—preprocess a set C of n convex simply-shaped fat objects in the plane, so that the k objects containing a query point p can be reported efficiently, (iii) bounded-size range searching— preprocess a set C of n convex fat polygons, so that the k objects intersecting a “not-too-large” query polygon can be reported efficiently, and (iv) bounded-size segment shooting—preprocess a set C as in (iii), so that the first object (if exists) hit by a “not-too-long” oriented query segment can be found efficiently. For the first three problems we construct data structures of size O(λ_s(n)log³n), where s is the maximum number of intersections between the boundaries of the (xy-projections) of any pair of objects, and λ_s(n) is the maximum length of (n, s) Davenport-Schinzel sequences. The data structure for the fourth problem is of size O(λ_s(n)log²n). The query time in the first problem is O(log⁴n), the query time in the second and third problems is O(log³n + klog²n), and the query time in the fourth problem is O(log³n).

We also present a simple algorithm for computing a depth order for a set as in (i), that is based on the solution to the vertical ray shooting problem. (A depth order for , if exists, is a linear order of , such that, if K₁, K₂ and K₁ lies vertically above K₂, then K₁ precedes K₂.) Unlike the algorithm of Agarwal et al. (1995) that might output a false order when a depth order does not exist, the new algorithm is able to determine whether such an order exists, and it is often more efficient in practical situations than the former algorithm.     

Generalization of the Gale–Ryser Theorem

We prove an inequality for the Kostka–Foulkes polynomials K_λ,μ(q) and give a criteria for the existence of a unique configuration of the given type (λ, μ). As a corollary, we obtain a nontrivial lower bound for the Kostka numbers which is a generalization the Gale–Ryser theorem on an existence of a (0,1)-matrix with given sums of rows and columns. A new proof of the Berenstein–Zelevinsky weight-multiplicity-one criteria is given.     

Constructions of (q, K, λ, t, Q) almost difference families

The concept of a (q, k, λ, t) almost difference family (ADF) has been introduced and studied by C. Ding and J. Yin as a useful generalization of the concept of an almost difference set. In this paper, we consider, more generally, (q, K, λ, t, Q)-ADFs, where K = {k₁, k₂, ..., k_r} is a set of positive integers and Q = (q₁, q₂,..., q_r) is a given block-size distribution sequence. A necessary condition for the existence of a (q, K, λ, t, Q)-ADF is given, and several infinite classes of (q, K, λ, t, Q)-ADFs are constructed.