Voting fairly: Transitive maximal intersecting families of sets (Q1584664)

The authors study the Maximum Intersecting Families (MIFs) of an \(n\)-element set \(X\). It is known that any MIF consists of \(2^{n-1}\) subsets, and computing their number as a function of \(n\) is a long-standing problem. Let \({\mathcal F}\) be a MIF on \(X\) and let \(\sigma:X\to X\) be a bijection. Denote \(\sigma({\mathcal F})=\{A\subseteq X : \sigma^{(-1)}(A)\in\mathcal F\}\). It can be shown that \(\sigma({\mathcal F})\) is a MIF on \(X\). If \({\mathcal F} = \sigma({\mathcal F})\), then \(\sigma\) is said to be an automorphism on \({\mathcal F}\). Denote by Aut\(({\mathcal F})\) the set of automorphisms of \({\mathcal F}\). It is easy to show that Aut\(({\mathcal F})\) is a permutation group on \(X\). If Aut\(({\mathcal F})\) is a transitive subgroup of Sym\((X)\) then \({\mathcal F}\) is called transitive. The main result of the paper is the enumeration of all transitive MIFs for \(n < 13\). The enumeration is given by means of tables, and the exact number of MIFs in question is computed. The authors mention several applications of MIFs, in particular to measuring the fairness of voting schemes.