Non-bossy social classification

We consider the problem of how societies should be partitioned into classes if individuals express their views about who should be put with whom in the same class. A non-bossy social aggregator depends only on those cells of the individual partitions the society members classify themselves in. This fact allows us to concentrate on a corresponding “opinion graph” for each profile of views. By means of natural sovereignty, liberalism, and equal treatment requirements, we characterize the non-bossy aggregators generating partitions in which the social classes are refinements of the weakly connected components of the opinion graph.     

Dominant strategies and restricted ballots with variable electorate

This paper considers dominant (uniformly best) voting strategies in a variable-electorate model for social choice with restricted ballot sets. A voter can have any weak preference order on the alternatives. A voter who partitions the alternatives into three or more indifference classes never has a dominant strategy. The paper specifies conditions on a social choice function that are necessary and sufficient for a voter who partitions the alternatives into two indifference classes to have a dominant strategy.     

Solving Partition Problems with Colour-Bipartitions

Polar, monopolar, and unipolar graphs are defined in terms of the existence of certain vertex partitions. Although it is polynomial to determine whether a graph is unipolar and to find whenever possible a unipolar partition, the problems of recognizing polar and monopolar graphs are both NP-complete in general. These problems have recently been studied for chordal, claw-free, and permutation graphs. Polynomial time algorithms have been found for solving the problems for these classes of graphs, with one exception: polarity recognition remains NP-complete in claw-free graphs. In this paper, we connect these problems to edge-coloured homomorphism problems. We show that finding unipolar partitions in general and finding monopolar partitions for certain classes of graphs can be efficiently reduced to a polynomial-time solvable 2-edge-coloured homomorphism problem, which we call the colour-bipartition problem. This approach unifies the currently known results on monopolarity and extends them to new classes of graphs.     

Opinion polarization by learning from social feedback

We explore a new mechanism to explain polarization phenomena in opinion dynamics in which agents evaluate alternative views on the basis of the social feedback obtained on expressing them. High support of the favored opinion in the social environment is treated as a positive feedback which reinforces the value associated to this opinion. In connected networks of sufficiently high modularity, different groups of agents can form strong convictions of competing opinions. Linking the social feedback process to standard equilibrium concepts we analytically characterize sufficient conditions for the stability of bi-polarization. While previous models have emphasized the polarization effects of deliberative argument-based communication, our model highlights an affective experience-based route to polarization, without assumptions about negative influence or bounded confidence.     

Idempotent Block Splitting on Partial Partitions,I: Isotone Operators

Image segmentation algorithms can be modelled as image-guided operators (maps) on the complete lattice of partitions of space, or on the one of partial partitions (i.e., partitions of subsets of the space). In particular region-splitting segmentation algorithms correspond to block splitting operators on the lattice of partial partitions, in other words anti-extensive operators that act by splitting each block independently. This first paper studies in detail block splitting operators and their lattice-theoretical and monoid properties; in particular we consider their idempotence (a requirement in image segmentation). We characterize block splitting openings (kernel operators) as operators splitting each block into its connected components according to a partial connection; furthermore, block splitting openings constitute a complete sublattice of the complete lattice of all openings on partial partitions. Our results underlie the connective approach to image segmentation introduced by Serra. The second paper will study two classes of non-isotone idempotent block splitting operators, that are also relevant to image segmentation.     

Classification of partitions of all triples on ten points into copies of Fano and affine planes

We continue our study of partitions of the full set of triples chosen from a v-set into copies of the Fano plane PG(2,2) (Fano partitions) or copies of the affine plane AG(2,3) (affine partitions) or into copies of both of these planes (mixed partitions). The smallest cases for which such partitions can occur are v=8 where Fano partitions exist, v=9 where affine partitions exist, and v=10 where both affine and mixed partitions exist. The Fano partitions for v=8 and the affine partitions for v=9 and 10 have been fully classified, into 11, two and 77 isomorphism classes, respectively. Here we classify (1) the sets of i pairwise disjoint affine planes for i=1,…,7, and (2) the mixed partitions for v=10 into their 22 isomorphism classes. We consider the ways in which these partitions relate to the large sets of AG(2,3).     

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.     

Multivalent preference structures

This paper presents a valence approach for assessing multiattribute utility functions. Unlike the decomposition approach which uses independence axioms on whole attributes to obtain utility representations, the valence approach partitions the elements of each attribute into classes on the basis of equivalent conditional preference orders. These partitions generate multivalent utility independence axioms that lead to additive-multiplicative and quasi-additive representation theorems for multiaatribute utility functions defined over product sets of equivalence classes. Preference interdependencies are thereby reflected in these classes, so attribute interactions are readily interpreted and the functional forms of the representations are kept simple.     

On the combinatorics of plethysm

We construct three (large, reduced) incidence algebras whose semigroups of multiplicative functions, under convolution, are anti-isomorphic, respectively, to the semigroups of what we call partitional, permutational and exponential formal power series without constant term, in infinitely many variables x = (x₁, x₂,…), under plethysm. We compute the Möbius function in each case. These three incidence algebras are the linear duals of incidence bialgebras arising, respectively, from the classes of transversals of partitions (with an order that we define), partitions compatible with permutations (with the usual refinement order), and linear transversals of linear partitions (with the order induced by that on transversals). We define notions of morphisms between partitions, permutations and linear partitions, respectively, whose kernels are defined to be, in each case, transversals, compatible partitions and linear transversals. We introduce, in each case, a pair of sequences of polynomials in x of binomial type, counting morphisms and monomorphisms, and obtain expressions for their connection constants, by summation and Möbius inversion over the corresponding posets of kernels.     

Automating the Partition of Indexes

Abstract

In this article we show how attention to the structure of a particular algebraic calculation can lead to the simple implementation of powerful computer algebra tools. The creation of partitions for a set of indexes is required for the implementation of many theoretical structures. This may be difficult to do by hand even when the number of indexes is only moderately large. These partitions arise through the action of differentiation and so we mimic differentiation in a computer algebra package to create partitions of indexes. The strategies employed are extended to the creation of complementary set partitions, their reduction to equivalence classes, and the implementation of Edgeworth expansions and the exlog relations.     

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     

A skein action of the symmetric group on noncrossing partitions

We introduce and study a new action of the symmetric group \({\mathfrak {S}}_n\) on the vector space spanned by noncrossing partitions of \(\{1, 2,\ldots , n\}\) in which the adjacent transpositions \((i, i+1) \in {\mathfrak {S}}_n\) act on noncrossing partitions by means of skein relations. We characterize the isomorphism type of the resulting module and use it to obtain new representation-theoretic proofs of cyclic sieving results due to Reiner–Stanton–White and Pechenik for the action of rotation on various classes of noncrossing partitions and the action of K-promotion on two-row rectangular increasing tableaux. Our skein relations generalize the Kauffman bracket (or Ptolemy relation) and can be used to resolve any set partition as a linear combination of noncrossing partitions in a \({\mathfrak {S}}_n\)-equivariant way.     

The complexity of computing metric distances between partitions

Quantitative measurement of the similarity of partitions is a problem of particular relevance to the social and behavioral sciences, where experimental procedures necessitate the analysis and comparison of partitions of objects. Since metrics used for this purpose vary considerably in computational complexity. I describe two related metric models that permit methodical enumeration of metrics which may be useful and computationally tractable. Twelve metrics on partitions are identified in this way. Five of them have appeared in the literature, while seven appear to be new. Four of them seem difficult to compute, but efficient algorithms for the remaining eight exist and exhibit time complexities ranging from O(n) to O(n³), where n is the number of objects in the partitions. These algorithms are all based on lattice- and graph-theoretic representations of the computational problems.     

Combinatorial Interpretations for Identities Using Chromatic Partitions

Czechoslovak Mathematical Journal - We provide combinatorial interpretations for three new classes of partitions, the so-called chromatic partitions. Using only combinatorial arguments, we show...     

A model of influence based on aggregation functions

The paper concerns a dynamic model of influence in which agents make a yes–no decision. Each agent has an initial opinion which he may change during different phases of interaction, due to mutual influence among agents. We investigate a model of influence based on aggregation functions. Each agent modifies his opinion independently of the others, by aggregating the current opinion of all agents. Our framework covers numerous existing models of opinion formation, since we allow for arbitrary aggregation functions. We provide a general analysis of convergence in the aggregation model and find all terminal classes and states. We show that possible terminal classes to which the process of influence may converge are terminal states (the consensus states and nontrivial states), cyclic terminal classes, and unions of Boolean lattices (called regular terminal classes). An agent is influential for another agent if the opinion of the first one matters for the latter. A generalization of influential agent to an irreducible coalition whose opinion matters for an agent is called influential coalition. The graph (hypergraph) of influence is a graphical representation of influential agents (coalitions). Based on properties of the hypergraphs of influence we obtain conditions for the existence of the different kinds of terminal classes. An important family of aggregation functions–the family of symmetric decomposable models–is discussed. Finally, based on the results of the paper, we analyze the manager network of Krackhardt.     

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.     

Localizing combinatorial properties of partitions

The purpose of this paper is to develop a framework for the analysis of combinatorial properties of partitions. Our focus is on the relation between global properties of partitions and their localization to subpartitions. First, we study properties that are characterized by their local behavior. Second, we determine sufficient conditions for classes of partitions to have a member that has a given property. These conditions entail the possibility of being able to move from an arbitrary partition in the class to one that satisfies the given property by sequentially satisfying local variants of the property. We apply our approach to several properties of partitions that include consecutiveness, nestedness, order-consecutiveness, full nestedness and balancedness, and we demonstrate its usefulness in determining the existence of optimal partitions that satisfy such properties.     

Regular partitions of dual polar spaces

We describe several classes of regular partitions of dual polar spaces and determine their associated parameters and eigenvalues. We also give some general methods for computing the eigenvalues of regular partitions of dual polar spaces.     

Adaptation to anisotropy and inhomogeneity via dyadic piecewise polynomial selection

This article is devoted to nonlinear approximation and estimation via piecewise polynomials built on partitions into dyadic rectangles. The approximation rate is studied over possibly inhomogeneous and anisotropic smoothness classes that contain Besov classes. Highlighting the interest of such a result in statistics, adaptation in the minimax sense to both inhomogeneity and anisotropy of a related multivariate density estimator is proved. Besides, that estimation procedure can be implemented with a computational complexity simply linear in the sample size.     

A Bijection for the Alperin Weight Conjecture in <Emphasis Type="Italic">S</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>

The Alperin weight conjecture states that if G is a finite group and p is a prime, then the number of irreducible Brauer characters of a group G should be equal to the number of conjugacy classes of p-weights of G. This conjecture is known to be true for the symmetric group S _n , however there is no explicit bijection given between the two sets. In this paper we develop an explicit bijection between the p-weights of S _n and a certain set of partitions that is known to have the same cardinality as the irreducible Brauer characters of S _n . We also develop some properties of this bijection, especially in relation to a certain class of partitions whose corresponding Specht modules over fields of characteristic p are known to be irreducible.