A diametric theorem for edges (Q1586122): Difference between revisions

The authors introduce and study the edge-diametric function \(E(n,d)\). For a set system \({\mathcal A}\), let \(f({\mathcal A})\) be the number of pairs of members of \(\mathcal A\) whose Hamming distance is 1. The function \(E(n,d)\) is defined to be the maximum \(f({\mathcal A})\), where \(\mathcal A\) ranges over set systems of diameter at most \(d\) (with respect to the Hamming metric) on an \(n\)-element set. The main result of this paper gives the precise values of \(E(n,d)\) and the associated optimal configurations for all admissible \(n\) and \(d\). This is related to a result of \textit{D. J. Kleitman} [J. Comb. Theory 1, 209-214 (1966; Zbl 0148.01105)] which gives the maximum size of a set system of diameter at most \(d\) on \(n\) elements (as a function of \(n\) and \(d\)).