scientific article; zbMATH DE number 2212132

From MaRDI portal
Publication:5694874





The paper presents a new approach to prove the Erdős-Ko-Rado theorem that tells that if \({\mathcal A}\subseteq {[n]\choose k}\) for \(k\leq n/2\) then \(| {\mathcal A}| \leq {n-1\choose k-1}\). An equivalent formulation is \(\mu_p({\mathcal A})\leq p\), where \(p\leq 1/2\) and \(\mu_p\) is the following product measure on \(\{0,1\}^n\): \(\mu_p(x)=p^{| x| }(1-p)^{n-| x| }\) with \(| x| =\sum_i x_i\). The proof introduces a special orthonormal basis for functions on \(\{0,1\}^n\) and uses it in the Fourier expansion of the characteristic function \(f\) of \(\mathcal A\) in terms of the above basis. Since \(f\) takes on only the values 0 and 1, the sum of squares of its Fourier coefficients is \(\mu_p({\mathcal A})\). Using this fact and an short lemma on the properties of the sums of the Fourier coefficients, the theorem follows in one line. The equality is only possible if \(f\) is a linear Boolean function depending on a single coordinate, which translates to all subsets of \(\mathcal A\) a common element \(i\in [n]\). For the entire collection see [Zbl 1064.00004].











This page was built for publication:

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