Partitions of a Polytope and Mappings of a Point Set to Facets

Three theorems of this paper generalize previous results of the author on conjectures of A. Bezdek and V.V. Proizvolov. They show the existence of mappings from a given point set to the set of facets of a given polytope that satistfy some special conditions. Developing the same technique, some results on convex polytope partitions are presented, two of them dealing with partitions with prescribed measures of parts. Then we prove a corollary on the existence of a possibly nonconvex polytope with a given set of vertices, containing given points in its interior. We also consider problems of the following type: find an assignment of vectors from a given set to the parts of a given convex partition of ℝⁿ so that the shifts of the parts by their corresponding vectors either do not intersect by interior points or cover ℝⁿ     

Euler-Mahonian statistics on ordered set partitions (II)

[E. Steingrímsson, Statistics on ordered partitions of sets, arXiv: math.CO/0605670] introduced several hard statistics on ordered set partitions and conjectured that their generating functions are related to the q-Stirling numbers of the second kind. In a previous paper, half of these conjectures have been proved by Ishikawa, Kasraoui and Zeng using the transfer-matrix method. In this paper, we shall give bijective proofs of all the conjectures of Steingrímsson. Our basic idea is to encode ordered set partitions by a kind of path diagrams and explore the rich combinatorial properties of the latter structure. As a bonus of our approach, we derive two new σ-partition interpretations of the p,q-Stirling numbers of the second kind introduced by Wachs and White. We also discuss the connections with MacMahon's theorem on the equidistribution of the inversion number and major index on words and give a partition version of his result.     

Combinatorial interpretations of congruences for the spt-function

Let spt(n) denote the total number of appearances of the smallest parts in all the partitions of n. In 1988, the second author gave new combinatorial interpretations of Ramanujan’s partition congruences mod 5, 7 and 11 in terms of a crank for weighted vector partitions. In 2008, the first author found Ramanujan-type congruences for the spt-function mod 5, 7 and 13. We give new combinatorial interpretations of the spt-congruences mod 5 and 7. These are in terms of the same crank but for a restricted set of vector partitions. The proof depends on relating the spt-crank with the crank of vector partitions and the Dyson rank of ordinary partitions. We derive a number of identities for spt-crank modulo 5 and 7. We prove the surprising result that all the spt-crank coefficients are nonnegative.     

Covariance Partition Priors: A Bayesian Approach to Simultaneous Covariance Estimation for Longitudinal Data

The estimation of the covariance matrix is a key concern in the analysis of longitudinal data. When data consist of multiple groups, it is often assumed the covariance matrices are either equal across groups or are completely distinct. We seek methodology to allow borrowing of strength across potentially similar groups to improve estimation. To that end, we introduce a covariance partition prior that proposes a partition of the groups at each measurement time. Groups in the same set of the partition share dependence parameters for the distribution of the current measurement given the preceding ones, and the sequence of partitions is modeled as a Markov chain to encourage similar structure at nearby measurement times. This approach additionally encourages a lower-dimensional structure of the covariance matrices by shrinking the parameters of the Cholesky decomposition toward zero. We demonstrate the performance of our model through two simulation studies and the analysis of data from a depression study. This article includes Supplementary Materials available online.     

On Potts Model Clustering,Kernel K-Means and Density Estimation

Many clustering methods, such as K -means, kernel K -means, and MNcut clustering, follow the same recipe: (i) choose a measure of similarity between observations; (ii) define a figure of merit assigning a large value to partitions of the data that put similar observations in the same cluster; and (iii) optimize this figure of merit over partitions. Potts model clustering represents an interesting variation on this recipe. Blatt, Wiseman, and Domany defined a new figure of merit for partitions that is formally similar to the Hamiltonian of the Potts model for ferromagnetism, extensively studied in statistical physics. For each temperature T, the Hamiltonian defines a distribution assigning a probability to each possible configuration of the physical system or, in the language of clustering, to each partition. Instead of searching for a single partition optimizing the Hamiltonian, they sampled a large number of partitions from this distribution for a range of temperatures. They proposed a heuristic for choosing an appropriate temperature and from the sample of partitions associated with this chosen temperature, they then derived what we call a consensus clustering: two observations are put in the same consensus cluster if they belong to the same cluster in the majority of the random partitions. In a sense, the consensus clustering is an “average” of plausible configurations, and we would expect it to be more stable (over different samples)than the configuration optimizing the Hamiltonian.

The goal of this article is to contribute to the understanding of Potts model clustering and to propose extensions and improvements: (1) We show that the Hamiltonian used in Potts model clustering is closely related to the kernel K -means and MNCutcriteria. (2) We propose a modification of the Hamiltonian penalizing unequal clustersizes and show that it can be interpreted as a weighted version of the kernel K -meanscriterion. (3) We introduce a new version of the Wolff algorithm to simulate configurations from the distribution defined by the penalized Hamiltonian, leading to penalized Potts model clustering. (4) We note a link between kernel based clustering methods and nonparametric density estimation and exploit it to automatically determine locally adaptive kernel bandwidths. (5) We propose a new simple rule for selecting a good temperature T.

As an illustration we apply Potts model clustering to gene expression data and compare our results to those obtained by model based clustering and a nonparametric dendrogram sharpening method.     

Orthogonal Partitions in Designed Experiments

A survey is given of the statistical theory of orthogonal partitions on a finite set. Orthogonality, closure under suprema, and one trivial partition give an orthogonal decomposition of the corresponding vector space into subspaces indexed by the partitions. These conditions plus uniformity, closure under infima and the other trivial partition give association schemes. Examples covered by the theory include Latin squares, orthogonal arrays, semilattices of subgroups, and partitions defined by the ancestral subsets of a partially ordered set (the poset block structures).Isomorphism, equivalence and duality are discussed, and the automorphism groups given in some cases. Finally, the ideas are illustrated by some examples of real experiments.Dedicated to Hanfried Lenz on the occasion of his 80th birthday.     

Orthogonal partitions in designed experiments

A survey is given of the statistical theory of orthogonal partitions on a finite set. Orthogonality, closure under suprema, and one trivial partition give an orthogonal decomposition of the corresponding vector space into subspaces indexed by the partitions. These conditions plus uniformity, closure under infima and the other trivial partition give association schemes. Examples covered by the theory include Latin squares, orthogonal arrays, semilattices of subgroups, and partitions defined by the ancestral subsets of a partially ordered set (the poset block structures).Isomorphism, equivalence and duality are discussed, and the automorphism groups given in some cases. Finally, the ideas are illustrated by some examples of real experiments.Dedicated to Hanfried Lenz on the occasion of his 80th birthday.     

An optimal algorithm for generating equivalence relations on a linear array of processors

We describe a cost-optimal parallel algorithm for enumerating all partitions (equivalence relations) of the set {1, ...,n}, in lexicographic order. The algorithm is designed to be executed on a linear array of processors. It usesn processors, each having constant size memory and each being responsible for producing one element of a given set partition. Set partitions are generated with constant delay leading to anO(B _n) time solution, whereB _n is the total number of set partitions. The same method can be generalized to enumerate some other combinatorial objects such as variations. The algorithm can be made adaptive, i.e. to run on any prespecified number of processors. To illustrate the model of parallel computation, a simple case of enumerating subsets of the set {1, ...,n}, having at mostm (n) elements is also described.The research is partialy supported by NSERC operating grant OGPIN 007.     

Sur les ensembles représentés par les partitions d'un entier n

Let n = n₁ + n₂ + … + n_j a partition Π of n. One will say that this partition represents the integer a if there exists a subsum n_il + n_i2 + … + n_il equal to a. The set (Π) is defined as the set of all integers a represented by Π. Let be a subset of the set of positive integers. We denote by p( ,n) the number of partitions of n with parts in , and by (( ,n) the number of distinct sets represented by these partitions. Various estimates for ( ,n) are given. Two cases are more specially studied, when is the set {1, 2, 4, 8, 16, …} of powers of 2, and when is the set of all positive integers. Two partitions of n are said to be equivalent if they represent the same integers. We give some estimations for the minimal number of parts of a partition equivalent to a given partition.     

On multiple pattern avoiding set partitions

We study classes of set partitions determined by the avoidance of multiple patterns, applying a natural notion of partition containment that has been introduced by Sagan. We say that two sets S and T of patterns are equivalent if for each n the number of partitions of size n avoiding all the members of S is the same as the number of those that avoid all the members of T.     

Group technology in production management: The short horizon planning level

We consider a set of parts divided into subsets called part types, determined in such a way that the parts belonging to the same part type are manufactured using the same sequence of tasks (i.e. the same working process). We are looking for a partition of the set of part types into subsets called part families, and for a partition of the set of tasks into subsets called production subsystems defined as follows: (1) the number of part families and the number of production subsystems are equal, (2) one (one only one) production subsystem corresponds to each part family, (3) one (and only one) part family corresponds to each production subsystem, (4) the previous partitions minimize the number of tasks performed in a production subsystem different from that which corresponds to the part family containing the part involved. We give a fast algorithm which leads to a good solution depending on the initial set of part families. We also propose an algorithm to find a ‘good’ initial set of part families.     

Comparing clusterings—an information based distance

This paper proposes an information theoretic criterion for comparing two partitions, or clusterings, of the same data set. The criterion, called variation of information (VI), measures the amount of information lost and gained in changing from clustering C to clustering C^′. The basic properties of VI are presented and discussed. We focus on two kinds of properties: (1) those that help one build intuition about the new criterion (in particular, it is shown the VI is a true metric on the space of clusterings), and (2) those that pertain to the comparability of VI values over different experimental conditions. As the latter properties have rarely been discussed explicitly before, other existing comparison criteria are also examined in their light. Finally we present the VI from an axiomatic point of view, showing that it is the only “sensible” criterion for comparing partitions that is both aligned to the lattice and convexely additive. As a consequence, we prove an impossibility result for comparing partitions: there is no criterion for comparing partitions that simultaneously satisfies the above two desirable properties and is bounded.     

Region configurations for realizability of lattice Piecewise-Linear models

Continuous Piecewise-Linear (PWL) functions can be represented by a scheme that selects adequately the linear components of the function without considering explicitly the boundaries. The representation method based on the Lattice Theory, that we call the lattice PWL model, is a form that fits that scheme. In this paper, two domain partitions are proposed that give rise to region configurations practically meaningful for the realizability of lattice models. In one of those partitions, each region is uniquely determined by one of the linear function. The other region configuration is derived from the rearrangement in ascending order of the linear components. Both configurations are discussed and connected with the domain partition generated by the set of boundaries, frequently considered when dealing with PWL functions. The realization method of lattice models is adapted to the three region configurations, comparing the efficiency of the resulting versions.     

Non-adaptability measures in the pseudo-questionnaires context

Measuring the degree of non-adaptability of a partition to a criterion, represented by a reference partition, is an essential step in pseudo-questionnaires theory. In this work we characterize axiomatically the measure of non-adaptability in a general context. We base it on pre-orders on the set of all the possible experiences (complete or incomplete partitions). The construction of this measure is crucial for practical applications. It can be done in a natural way starting from the atoms of the partitions and constructing the non-adaptability measure by a process of successive aggregations made by suitable aggregation operators.     

On the Number of Birch Partitions

Birch and Tverberg partitions are closely related concepts from discrete geometry. We show two properties for the number of Birch partitions: Evenness and a lower bound. This implies the first nontrivial lower bound for the number of Tverberg partitions that holds for arbitrary q, where q is the number of partition blocks. The proofs are based on direct arguments and do not use the equivariant method from topological combinatorics.     

Large sample properties of estimates of a discrete grade of membership model

Increasingly, fuzzy partitions are being used in multivariate classification problems as an alternative to the crisp classification procedures commonly used. One such fuzzy partition, the grade of membership model, partitions individuals into fuzzy sets using multivariate categorical data. Although the statistical methods used to estimate fuzzy membership for this model are based on maximum likelihood methods, large sample properties of the estimation procedure are problematic for two reasons. First, the number of incidental parameters increases with the size of the sample. Second, estimated parameters fall on the boundary of the parameter space with non-zero probability. This paper examines the consistency of the likelihood approach when estimating the components of a particular probability model that gives rise to a fuzzy partition. The results of the consistency proof are used to determine the large sample distribution of the estimates. Common methods of classifying individuals based on multivariate observations attempt to place each individual into crisply defined sets. The fuzzy partition allows for individual to individual heterogeneity, beyond simply errors in measurement, by defining a set of pure type characteristics and determining each individual's distance from these pure types. Both the profiles of the pure types and the heterogeneity of the individuals must be estimated from data. These estimates empirically define the fuzzy partition. In the current paper, this data is assumed to be categorical data. Because of the large number of parameters to be estimated and the limitations of categorical data, one may be concerned about whether or not the fuzzy partition can be estimated consistently. This paper shows that if heterogeneity is measured with respect to a fixed number of moments of the grade of membership scores of each individual, the estimated fuzzy partition is consistent.     

Central Limit Theorem for Random Strict Partitions

We consider the set of all partitions of a number n into distinct summands (the so-called strict partitions) with the uniform distribution on it and study fluctuations of a random partition near its limit shape, for large n. The use of geometrical language allows us to state the problem in terms of the limit behavior of random step functions (Young diagrams). A central limit theorem for such functions is proven. Our method essentially uses the notion of large canonical ensemble of partitions. Bibliography: 7 titles.     

Data structures for maintaining set partitions

Efficiently maintaining the partition induced by a set of features is an important problem in building decision‐tree classifiers. In order to identify a small set of discriminating features, we need the capability of efficiently adding and removing specific features and determining the effect of these changes on the induced classification or partition. In this paper we introduce a variety of randomized and deterministic data structures to support these operations on both general and geometrically induced set partitions. We give both Monte Carlo and Las Vegas data structures that realize near‐optimal time bounds and are practical to implement. We then provide a faster solution to this problem in the geometric setting. Finally, we present a data structure that efficiently estimates the number of partitions separating elements. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

Optimal partitioning of a measurable space into countably many sets

Summary A notion of an optimal partition of a measurable space into countably many sets according to given nonatomic probability measures is defined. It is shown that the set of optimal partitions is nonempty. Bounds for the optimal value are given and the set of optimal partitions is characterized. Finally, an example related to statistical decision theory is presented.