On nearly self-conjugate partitions of a finite set
type: Item
instance of: scholarly article
title: On nearly self-conjugate partitions of a finite set
zbMATH Open document ID: 0892.05005
DOI: 10.1016/S0012-365X(94)00066-R
author: Honghui Wan
published in: Discrete Mathematics
publication date: 1998-07-19T00:00:00Z
review text: Let \(P=\{P_1,P_2,\dots,P_k\}\) be a partition of \([n]=\{1,2,\dots,n\}\). Let \(C(i)\) denote the cardinality of the subset \(P_j\) to which \(i\) belongs. Suppose that \(P'=\{P_1',P_2',\dots,P_k'\}\) is a second partition of \([n]\) and define \(C'(i)\) analogously. The partitions \(P\) and \(P'\) are called conjugate if \((C(i),C'(i))\) determine \(i\). If in addition \(| P_j|=| P_j'|\) for all \(j\) then \(P\) is called nearly self-conjugate. This notion of conjugate partitions appeared in the short solution by \textit{R. L. Graham} [J. Comb. Theory 1, 215-223 (1966; Zbl 0144.00404)] of a problem originally arising in circuit theory. There are two questions which Graham addressed (but provided only partial answers): (1) Given a partition \(P\), how can one read off immediately if there is a partition \(P'\) conjugate to \(P\)? (2) Which conditions must hold for \(m\), such that there exist a pair \(P,P'\) of conjugate partitions with maximal part size \(m\)? The author of the paper under review uses an incidence matrix approach and the Gale-Ryser theorem to answer question (1) completely: He gives necessary and sufficient conditions on \(P\) such that there is a partition \(P'\) conjugate to \(P\). Moreover, he shows that if \(m(m+1)/2\leq n\leq \sum _{1\leq j\leq m} ^{}j\cdot \lfloor m/j\rfloor\) then there exists even a nearly self-conjugate partition \(P\) of \([n]\) with maximal part size \(m\), thus answering question (2).
Mathematics Subject Classification ID: 05A18
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 05B20
zbMATH DE Number: 1110024
zbMATH Keywords: set partitions
zbMATH Keywords: conjugate partitions
zbMATH Keywords: Gale-Ryser theorem
reviewed by: C. Krattenthaler
MaRDI profile type: Publication
cites work: A test for conjugacy of partitions of finite sets
cites work: A theorem on flows in networks
cites work: On partitions of a finite set
cites work: Combinatorial Properties of Matrices of Zeros and Ones
cites work: Q5187402
cites work: On the number of tournaments with prescribed score vector
cites work: Q3807359
full work available at URL: s0012-365x(94)00066-r
OpenAlex ID: W1990092166
Recommended article: Q3691681
Recommended article: Combinatorial proofs of some enumeration identities
Recommended article: Q4702104
Recommended article: Q4456726
Recommended article: Q4995463
Recommended article: Nearly self-conjugate integer partitions
Recommended article: Q4542340
Recommended article: Pairing conjugate partitions by residue classes
Recommended article: Q5026991
Recommended article: Recursively Self-Conjugate Partitions
description: scientific article; zbMATH DE number 1110024