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

    Identifiers