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.     

Closures on partial partitions from closures on sets

Jordens and Sturm investigated the link between closure systems on sets and closure systems on partitions. We extend that study to the wider framework of partial partitions, and highlight better the relation between these two families of closure systems. Then we consider the construction of a closure operator on partial partitions by the iterated application a set operator to the blocks of a partial partition; the resulting closure system fits into our framework.     

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.     

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.     

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.     

On graphical partitions and planarity

Chvátal gave a necessary condition for a partition to have a planar realization. It is of interest to find: (i) partitions which satisfy the condition of the theorem but have no planar realization, and also (ii) partitions which satisfy the condition and have only planar realizations. We give a list of all such partitions with 6, 7, 8 and 9 elements. We also give an algorithm for generating all graphs with a given partition, an algorithm for generating all subcompositions of a given composition and some general classes of partitions which have planar realizations only and some which have non-planar realizations only.     

Some set partition statistics in non-crossing partitions and generating functions

In this paper we shall give the generating functions for the enumeration of non-crossing partitions according to some set partition statistics explicitly, which are based on whether a block is singleton or not and is inner or outer. Using weighted Motzkin paths, we find the continued fraction form of the generating functions. There are bijections between non-crossing partitions, Dyck paths and non-nesting partitions, hence we can find applications in the enumeration of Dyck paths and non-nesting partitions. We shall also study the integral representation of the enumerating polynomials for our statistics. As an application of integral representation, we shall give some remarks on the enumeration of inner singletons in non-crossing partitions, which is equivalent to one of udu's at high level in Dyck paths investigated in [Y. Sun, The statistic “number of udu's” in Dyck paths, Discrete Math. 284 (2004) 177-186].     

Topological Properties of Neumann Domains

A Laplacian eigenfunction on a two-dimensional manifold dictates some natural partitions of the manifold; the most apparent one being the well studied nodal domain partition. An alternative partition is revealed by considering a set of distinguished gradient flow lines of the eigenfunction—those which are connected to saddle points. These give rise to Neumann domains. We establish complementary definitions for Neumann domains and Neumann lines and use basic Morse homology to prove their fundamental topological properties. We study the eigenfunction restrictions to these domains. Their zero set, critical points and spectral properties allow to discuss some aspects of counting the number of Neumann domains and estimating their geometry.     

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 ℝⁿ     

How to determine a partition up to conjugation using multisets of hook lengths

If two partitions are conjugate, their multisets of hook lengths are the same. Then one may wonder whether the multiset of hook lengths of a partition determines a partition up to conjugation. The answer turns out to be no. However, we may add an extra condition under which a given multiset of hook lengths determines a partition uniquely up to conjugation. Herman-Chung, and later Morotti found such a condition. We give an alternative proof of Morotti’s theorem and generalize it.     

On the number of equivalence classes arising from partition involutions II

In this paper, we consider the pseudo-conjugation and its variations on the sets of partitions with restricted cranks and involutions on Frobenius symbols. We give several partition identities revealing relations between the number of equivalence classes in the set of partitions arising from an involution and the number of partitions satisfying a certain parity condition.     

The walk partition and colorations of a graph

We study the partitions of a graph G with vertices labeled 1,2,…,n. A matrix notation for partitions is devised which reflects a partial order among partitions and provides a matrix characterization (in terms of the adjacency matrix A of G) of a coloration or equitable partition. An especially useful partition is one based on the number of walks issuing from each vertex. This is not generally a coloration (sufficient conditions are given) but nevertheless plays a special role relative to colorations. The spectrum of G, Sp(G), has a “main part”, the set of eigenvalues with an eigenvector not orthogonal to e (the column of 1s). We disprove a conjecture of Harary and Schwenk about the main part of the spectrum and prove an alternate characterization. The walk partition appears here and also in a relation between the main parts of the spectra of G and ?, its complement.     

Partition Identities Involving Gaps and Weights,II

In this second paper under the same title, some more weighted representations are obtained for various classical partition functions including p(n), the number of unrestricted partitions ofn , Q(n), the number of partitions ofn into distinct parts and the Rogers-Ramanujan partitions ofn (of both types). The weights derived here are given either in terms of congruence conditions satisfied by the parts or in terms of chains of gaps between the parts. Some new connections between partitions of the Rogers-Ramanujan, Schur and Göllnitz–Gordon type are revealed.     

Cranks andt-cores

Summary New statistics on partitions (calledcranks) are defined which combinatorially prove Ramanujan's congruences for the partition function modulo 5, 7, 11, and 25. Explicit bijections are given for the equinumerous crank classes. The cranks are closely related to thet-core of a partition. Usingq-series, some explicit formulas are given for the number of partitions which aret-cores. Some related questions for self-conjugate and distinct partitions are discussed.This work was partially supported by NSF grant DMS: 8700995Oblatum 16-IX-1989     

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     

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.     

Consensus of partitions : a constructive approach

Given a profile (family) ?? of partitions of a set of objects or items X, we try to establish a consensus partition containing a maximum number of joined or separated pairs in X that are also joined or separated in the profile. To do so, we define a score function, S _?? associated to any partition on X. Consensus partitions for ?? are those maximizing this function. Therefore, these consensus partitions have the median property for the profile and the symmetric difference distance. This optimization problem can be solved, in certain cases, by integer linear programming. We define a polynomial heuristic which can be applied to partitions on a large set of items. In cases where an optimal solution can be computed, we show that the partitions built by this algorithm are very close to the optimum which is reached in practically all the cases, except for some sets of bipartitions.     

Comparing partitions of two sets of units based on the same variables

We propose a procedure based on a latent variable model for the comparison of two partitions of different units described by the same set of variables. The null hypothesis here is that the two partitions come from the same underlying mixture model. We define a method of “projecting” partitions using a supervised classification method: once one partition is taken as a reference; the individuals of the second data set are allocated to the clusters of the reference partition; it gives two partitions of the same units of the second data set: the original and the projected one and we evaluate their difference by usual measures of association. The empirical distributions of the association measures are derived by simulation.