A multiset hook length formula and some applications

A multiset hook length formula for integer partitions is established by using combinatorial manipulation. As special cases, we rederive three hook length formulas, two of them obtained by Nekrasov–Okounkov, the third one by Iqbal, Nazir, Raza and Saleem, who have made use of the cyclic symmetry of the topological vertex. A multiset hook-content formula is also proved.     

Self-conjugate partitions with the same disparity

We give a bijection between the set of ordinary partitions and that of self-conjugate partitions with some restrictions. Also, we show the relationship between hook lengths of a self-conjugate partition and its corresponding partition via the bijection. As a corollary, we give new combinatorial interpretations for the Catalan number and the Motzkin number in terms of self-conjugate simultaneous core partitions.     

Hook lengths and shifted parts of partitions

Some conjectures on partition hook lengths, recently stated by the author, have been proved and generalized by Stanley, who also needed a formula by Andrews, Goulden and Jackson on symmetric functions to complete his derivation. Another identity on symmetric functions can be used instead. The purpose of this note is to prove it.     

The Generalized Multiset Sampler

The multiset sampler, an MCMC algorithm recently proposed by Leman and coauthors, is an easy-to-implement algorithm which is especially well-suited to drawing samples from a multimodal distribution. We generalize the algorithm by redefining the multiset sampler with an explicit link between target distribution and sampling distribution. The generalized formulation replaces the multiset with a K-tuple, which allows us to use the algorithm on unbounded parameter spaces, improves estimation, and sets up further extensions to adaptive MCMC techniques. Theoretical properties of the algorithm are provided and guidance is given on its implementation. Examples, both simulated and real, confirm that the generalized multiset sampler provides a simple, general and effective approach to sampling from multimodal distributions. Supplementary materials for this article are available online.     

Partitions of multisets

A multiset is a set with repeated elements. There are four distinct partition numbers to consider, unlike the classical set partition case which involves only Stirling numbers of the second kind. Using inclusion-exclusion, we obtain generating functions when each element appears exactly r = 1, 2 or 3 times. The case r = 1 is classical and r = 2 was studied by Comtet and Baróti using other methods. Our approach also leads to asymptotic formulae for the total number of partitions of multisets in which the repetition of elements is bounded. Another approach to multiset enumeration, using de Brujin's theorem for group reduced distributions, is described.     

Topological approximations of multisets

Rough set theory is a powerful mathematical tool for dealing with inexact, uncertain or vague information. The core concept of rough set theory are information systems and approximation operators of approximation spaces. In this paper, we define and investigate three types of lower and upper multiset approximations of any multiset. These types based on the multiset base of multiset topology induced by a multiset relation. Moreover, the relationships between generalized rough msets and mset topologies are given. In addition, an illustrative example is given to illustrate the relationships between different types of generalized definitions of rough multiset approximations.     

The complexity of the Specht modules corresponding to hook partitions

We show that the complexity of the Specht module corresponding to any hook partition is the p-weight of the partition. We calculate the variety and the complexity of the signed permutation modules. Let E _s be a representative of the conjugacy class containing an elementary abelian p-subgroup of a symmetric group generated by s disjoint p-cycles. We give formulae for the generic Jordan types of signed permutation modules restricted to E _s and of Specht modules corresponding to hook partitions μ restricted to E _s where s is the p-weight of μ.      

A theory for the multiset sampler

The multiset sampler (MSS) can be viewed as a new data augmentation scheme and it has been applied successfully to a wide range of statistical inference problems. The key idea of the MSS is to augment the system with a multiset of the missing components, and construct an appropriate joint distribution of the parameters of interest and the missing components to facilitate the inference based on Markov chain Monte Carlo. The standard data augmentation strategy corresponds to the MSS with multiset size one. This paper provides a theoretical comparison of the MSS with different multiset sizes. We show that the MSS converges to the target distribution faster as the multiset size increases. This explains the improvement in convergence rate for the MSS with large multiset sizes over the standard data augmentation scheme.     

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.     

A generalization of Dijkstra's shortest path algorithm with applications to VLSI routing

We generalize Dijkstra's algorithm for finding shortest paths in digraphs with non-negative integral edge lengths. Instead of labeling individual vertices we label subgraphs which partition the given graph. We can achieve much better running times if the number of involved subgraphs is small compared to the order of the original graph and the shortest path problems restricted to these subgraphs is computationally easy.As an application we consider the VLSI routing problem, where we need to find millions of shortest paths in partial grid graphs with billions of vertices. Here, our algorithm can be applied twice, once in a coarse abstraction (where the labeled subgraphs are rectangles), and once in a detailed model (where the labeled subgraphs are intervals). Using the result of the first algorithm to speed up the second one via goal-oriented techniques leads to considerably reduced running time. We illustrate this with a state-of-the-art routing tool on leading-edge industrial chips.     

Projection-forcing multisets of weight changes

Let F be a finite field. A multiset S of integers is projection-forcing if for every linear function ?:Fn→Fm whose multiset of weight changes is S, ? is a coordinate projection up to permutation and scaling of entries. The MacWilliams Extension Theorem from coding theory says that S={0,0,…,0} is projection-forcing. We give a (super-polynomial) algorithm to determine whether or not a given S is projection-forcing. We also give a condition that can be checked in polynomial time that implies that S is projection-forcing. This result is a generalization of the MacWilliams Extension Theorem and work by the first author.     

The Hillman-Grassl correspondence and the enumeration of reverse plane partitions

Hillman and Grassl have devised a correspondence between reverse plane partitions and nonnegative integer arrays of the same shape that allowed them to easily enumerate reverse plane partitions and provided a combinatorial connection between hook lengths and plane partitions. In this work, a collection of properties of this correspondence are presented, including two characterizations that relate this map to the familiar Schensted-Knuth correspondence. These properties are used to derive simple expressions for the generating functions of reverse plane partitions and symmetric reverse plane partitions with respect to sums along the diagonals. Equally general results are obtained for shifted reverse plane partitions using a new type of hook, thereby proving a conjecture of Stanley.     

On the reconstruction of the degree sequence

Harary's edge reconstruction conjecture states that a graph G=(V,E) with at least four edges is uniquely determined by the multiset of its edge-deleted subgraphs, i.e. the graphs of the form G−e for e∈E. It is well-known that this multiset uniquely determines the degree sequence of a graph with at least four edges. In this note we generalize this result by showing that the degree sequence of a graph with at least four edges is uniquely determined by the set of the degree sequences of its edge-deleted subgraphs with one well-described class of exceptions. Moreover, the multiset of the degree sequences of the edge-deleted subgraphs always allows one to reconstruct the degree sequence of the graph.     

The Self-Multiset Sampler

The multiset sampler has been shown to be an effective algorithm to sample from complex multimodal distributions, but the multiset sampler requires that the parameters in the target distribution can be divided into two parts: the parameters of interest and the nuisance parameters. We propose a new self-multiset sampler (SMSS), which extends the multiset sampler to distributions without nuisance parameters. We also generalize our method to distributions with unbounded or infinite support. Numerical results show that the SMSS and its generalization have a substantial advantage in sampling multimodal distributions compared to the ordinary Markov chain Monte Carlo algorithm and some popular variants. Supplemental materials for the article are available online.     

Symmetric nonnegative realizability via partitioned majorization

A sufficient condition for symmetric nonnegative realizability of a spectrum is given in terms of (weak) majorization of a partition of the negative eigenvalues by a selection of the positive eigenvalues. If there are more than two positive eigenvalues, an additional condition, besides majorization, is needed on the partition. This generalizes observations of Suleǐmanova and Loewy about the cases of one and two positive eigenvalues, respectively. It may be used to provide insight into realizability of 5-element spectra and beyond.     

Generalizations of Nekrasov-Okounkov Identity

Nekrasov-Okounkov identity gives a product representation of the sum over partitions of a certain function of partition hook length. In this paper, we give several generalizations of the Nekrasov-Okounkov identity using the cyclic symmetry of the topological vertex.     

Enumerating 3-manifolds with lengths up to 9 by a canonical order

On previous works, we enumerated the prime links with lengths up to 10 and the prime link exteriors with lengths up to 9. In this paper, we make an enumeration of the first 133 closed 3-manifolds which are the 3-manifolds with lengths up to 9 by using the enumeration of the prime link exteriors.     

Multiset Model Selection

Model selection algorithms are required to efficiently traverse the space of models. In problems with high-dimensional and possibly correlated covariates, efficient exploration of the model space becomes a challenge. To overcome this, a multiset is placed on the model space to enable efficient exploration of multiple model modes with minimal tuning. The multiset model selection (MSMS) framework is based on independent priors for the parameters and model indicators on variables. Posterior model probabilities can be easily obtained from multiset averaged posterior model probabilities in MSMS. The effectiveness of MSMS is demonstrated for linear and generalized linear models. Supplementary material for this article is available online.