Vertex Algebras and Combinatorial Identities

In the 1980's, J. Lepowsky and R. Wilson gave a Lie-theoretic interpretation of Rogers–Ramanujan identities in terms of level 3 representations of affine Lie algebra sl(2,C)~. When applied to other representations and affine Lie algebras, Lepowsky and Wilson's approach yielded a series of other combinatorial identities of the Rogers–Ramanujan type. At about the same time, R. Baxter rediscovered Rogers–Ramanujan identities within the context of statistical mechanics. The work of R. Baxter initiated another line of research which yielded numerous combinatorial and analytic generalizations of Rogers–Ramanujan identities. In this note, we describe some ideas and results related to Lepowsky and Wilson's approach and indicate the connections with some results in combinatorics and statistical physics.     

An algorithmic sign-reversing involution for special rim-hook tableaux

Eğecioğlu and Remmel [Linear Multilinear Algebra 26 (1990) 59–84] gave an interpretation for the entries of the inverse Kostka matrix K⁻¹ in terms of special rim-hook tableaux. They were able to use this interpretation to give a combinatorial proof that KK⁻¹=I but were unable to do the same for the equation K⁻¹K=I. We define an algorithmic sign-reversing involution on rooted special rim-hook tableaux which can be used to prove that the last column of this second product is correct. In addition, following a suggestion of Chow [preprint, math.CO/9712230, 1997] we combine our involution with a result of Gasharov [Discrete Math. 157 (1996) 193–197] to give a combinatorial proof of a special case of the (3+1)-free Conjecture of Stanley and Stembridge [J. Combin. Theory Ser. A 62 (1993) 261–279].     

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 note on q-Eulerian numbers

The paper contains a combinatorial interpretation of the q-Eulerian numbers suggested by H. O. Foulkes' combinatorial interpretation of the ordinary Eulerian numbers. Some applications are also given.     

Weighted Ehrhart theory and orbifold cohomology

We introduce the notion of a weighted δ-vector of a lattice polytope. Although the definition is motivated by motivic integration, we study weighted δ-vectors from a combinatorial perspective. We present a version of Ehrhart Reciprocity and prove a change of variables formula. We deduce a new geometric interpretation of the coefficients of the Ehrhart δ-vector. More specifically, they are sums of dimensions of orbifold cohomology groups of a toric stack.     

Combinatorial interpretations of the q-Faulhaber and q-Salié coefficients

Recently, Guo and Zeng discovered two families of polynomials featuring in a q-analogue of Faulhaber's formula for the sums of powers and a q-analogue of Gessel-Viennot's formula involving Salié's coefficients for the alternating sums of powers. In this paper, we show that these are polynomials with symmetric, nonnegative integral coefficients by refining Gessel-Viennot's combinatorial interpretations.     

Existence theorem and algorithm for a general implicit variational inequality in Banach space

By using the generalized f-projection operator, the existence theorem of solutions for the general implicit variational inequality GIVI(T-ξ,K) is proved without assuming the monotonicity of operators in reflexive and smooth Banach space. An iterative algorithm for approximating solution of the general implicit variational inequality is suggested also, and the convergence for this iterative scheme is shown. These theorems extend the corresponding results of Wu and Huang [K.Q. Wu, N.J. Huang, Comput. Math. Appl. 54 (2007) 399–406], Wu and Huang [K.Q. Wu, N.J. Huang, Bull. Austral. Math. Soc. 73 (2006) 307–317], Zeng and Yao [L.C. Zeng, J.C. Yao, J. Optimiz. Theory Appl. 132 (2) (2007) 321–337] and Li [J. Li, J. Math. Anal. Appl. 306 (2005) 55–71].     

Bilateral truncated Jacobi’s identity

Recently, Andrews and Merca considered the truncated version of Euler’s pentagonal number theorem and obtained a non-negative result on the coefficients of this truncated series. Guo and Zeng showed the coefficients of two truncated Gauss’ identities are non-negative and they conjectured that truncated Jacobi’s identity also has non-negative coefficients. Mao provided a proof of this conjecture by using an algebraic method. In this paper, we consider bilateral truncated Jacobi’s identity and show that when the upper and lower bounds of the summation satisfy some certain restrictions, then this bilateral truncated identity has non-negative coefficients. As a corollary, we show the conjecture of Guo and Zeng holds. Our proof is purely combinatorial and mainly based on a bijection for Jacobi’s identity.     

Tight spans of distances and the dual fractionality of undirected multiflow problems

In this paper, we give a complete characterization of the class of weighted maximum multiflow problems whose dual polyhedra have bounded fractionality. This is a common generalization of two fundamental results of Karzanov. The first one is a characterization of commodity graphs H for which the dual of maximum multiflow problem with respect to H has bounded fractionality, and the second one is a characterization of metrics d on terminals for which the dual of metric-weighed maximum multiflow problem has bounded fractionality. A key ingredient of the present paper is a nonmetric generalization of the tight span, which was originally introduced for metrics by Isbell and Dress. A theory of nonmetric tight spans provides a unified duality framework to the weighted maximum multiflow problems, and gives a unified interpretation of combinatorial dual solutions of several known min–max theorems in the multiflow theory.     

Partially 2-colored permutations and the Boros–Moll polynomials

We find a combinatorial setting for the coefficients of the Boros–Moll polynomials P _m (a) in terms of partially 2-colored permutations. Using this model, we give a combinatorial proof of a recurrence relation on the coefficients of P _m (a). This approach enables us to give a combinatorial interpretation of the log-concavity of P _m (a) which was conjectured by Moll and confirmed by Kauers and Paule.     

On a combinatorial theorem related to a theorem of G. Szegö

In 1954, M. Kac discovered a probabilistic interpretation of a theorem of G. Szegö of Toeplitz matrices and demonstrated that this theorem can be provedin an elementary way by using a combinatorial identify of G. A. Hunt. In this paper Hunt's combinatorial identity is derived from a more general combinatorial result.     

Higher order spt-functions

Andrews? spt-function can be written as the difference between the second symmetrized crank and rank moment functions. Using the machinery of Bailey pairs a combinatorial interpretation is given for the difference between higher order symmetrized crank and rank moment functions. This implies an inequality between crank and rank moments that was only known previously for sufficiently large n and fixed order. This combinatorial interpretation is in terms of a weighted sum of partitions. A number of congruences for higher order spt-functions are derived.     

On a problem of Erdős on integers, none of which divides the product of others

Erdős estimated the maximal number of integers selected from {1,2,…,N}, so that none of them divides the product of two others. In this paper, Erdős’ problem is extended to sets of integers such that none of them divides the product of k others. The proofs use combinatorial results.     

Bayesian calibration in the estimation of the age of rhinoceros

In this paper the Bayesian approach for nonlinear multivariate calibration will be illustrated. This goal will be achieved by applying the Gibbs sampler to the rhinoceros data given by Clarke (1992, Biometrics, 48(4), 1081–1094). It will be shown that the point estimates obtained from the profile likelihoods and those calculated from the marginal posterior densities using improper priors will in most cases be similar.     

Constructions of optimal GDRP’s of type

Generalized doubly resolvable packings (GDRPs) represent a combinatorial characterization of constant composition codes (CCCs). In this paper, we develop a number of general constructions of GDRPs of type λ¹μ^m−1. As a consequence, a new series of optimal CCCs is obtained.     

A Generalization of Noncommuting Graph via Automorphisms of a Group

Let G be a group. By using a family 𝒜 of subsets of automorphisms of G, we introduced a simple graph Γ_𝒜(G), which is a generalization of the non-commuting graph. In this paper, we study the combinatorial properties of Γ_𝒜(G).     

A Graph Theoretic Expansion Formula for Cluster Algebras of Classical Type

In this paper we give a graph theoretic combinatorial interpretation for the cluster variables that arise in most cluster algebras of finite type with bipartite seed. In particular, we provide a family of graphs such that a weighted enumeration of their perfect matchings encodes the numerator of the associated Laurent polynomial while decompositions of the graphs correspond to the denominator. This complements recent work by Schiffler and Carroll-Price for a cluster expansion formula for the A _n case while providing a novel interpretation for the B _n , C _n , and D _n cases.     

A New Way of Using Semidefinite Programming with Applications to Linear Equations mod p

We introduce a new method of constructing approximation algorithms for combinatorial optimization problems using semidefinite programming. It consists of expressing each combinatorial object in the original problem as a constellation of vectors in the semidefinite program. When we apply this technique to systems of linear equations mod p with at most two variables in each equation, we can show that the problem is approximable within (1 − κ(p))p, where κ(p) > 0 for all p. Using standard techniques, we also show that it is NP-hard to approximate the problem within a constant ratio, independent of p.     

Singular Polynomials of Generalized Kasteleyn Matrices

Kasteleyn counted the number of domino tilings of a rectangle by considering a mutation of the adjacency matrix: a Kasteleyn matrix K. In this paper we present a generalization of Kasteleyn matrices and a combinatorial interpretation for the coefficients of the characteristic polynomial of KK* (which we call the singular polynomial), where K is a generalized Kasteleyn matrix for a planar bipartite graph. We also present a q-version of these ideas and a few results concerning tilings of special regions such as rectangles.     

Hunting for a Smaller Convex Subdifferential

Certain useful basic results of the gradient (in the smooth case), the Clarkesubdifferential, the Michel–Penot subdifferential, which is also known asthe "small" subdifferential, and the directional derivative(in the nonsmooth case) are stated and discussed. One of the advantages ofthe Michel–Penot subdifferential is the fact that it is in general "smaller"than the Clarke subdifferential. In this paper it is shown that there existsubdifferentials which may be smaller than the Michel–Penot subdifferentialandwhich have certain useful calculus. It isfurther shown that in the case of quasidifferentiability, the Michel–Penotsubdifferential enjoys calculus whichhold for the Clarke subdifferential only in the regular case.