On nearly self-conjugate partitions of a finite set (Q1377761)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On nearly self-conjugate partitions of a finite set |
scientific article |
Statements
On nearly self-conjugate partitions of a finite set (English)
0 references
19 July 1998
0 references
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).
0 references
set partitions
0 references
conjugate partitions
0 references
Gale-Ryser theorem
0 references