Extremal systems with upper-bounded odd intersections
Let \(X\) be an \(n\)-element set and let \(\mathcal S\) be a family of subsets of \(X\). We say that \(\mathcal S\) is an \(s\)-family if, for each \(S\in{\mathcal S}\), \(|\{T\in{\mathcal S}:|S\cap T|\) is odd\(\}|<s\). \(m_s(n)\) is then the size of a largest \(s\)-family of an \(n\)-set. [\(m_0(n)\) is the size of a largest collection of subsets of an \(n\)-set with all pairwise intersections even.] The main result of this paper is a slight generalization of the following theorem: (1) If \(n\) is odd and \(s<{2^{\lfloor n/2\rfloor}- 2^{[n/2]-d}\over 2^{2d+1}-2}\) where \(d=\left\lceil{\log_2(n+1)-1\over 2}\right\rceil\), then \(m_s(n)= 2^{\lfloor n/2\rfloor}+s\); if \(n\) is even and \(s<{2^{n/2}- 2^{n/2-d-1}\over 2^{2d}-1}\) where \(d=\left\lceil{\log_2(n+ 1)\over 2}\right\rceil\), then \(m_s(n)= 2^{\lfloor n/2\rfloor}\). (2) For every \(n\) and \(s\), we have \(m_s(n)\leq 2s+{1\over 2}+\sqrt{2^n- 2s+{5\over 4}}\). If \(s\) satisfies \(2^n-2s= 2^m\), \(m<n- 1\), then the number of sets in an \(s\)-family cannot exceed \(2s+ 2^{m-{n-1\over 2}}\).
scientific article; zbMATH DE number 1029269