Voting fairly: Transitive maximal intersecting families of sets

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.

Recommendations

Cites work

Cited in

(7)

Describes a project that uses

Uses Software

Caml

This page was built for publication: Voting fairly: Transitive maximal intersecting families of sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1584664)