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}}\).
- Extremal set systems with weakly restricted intersections
- Extremal n-systems of sets
- Extremal results for algebraic linear interval systems
- Publication:5750908
- scientific article; zbMATH DE number 863493
- scientific article; zbMATH DE number 4164914
- Extremal set systems with restricted \(k\)-wise intersections.
- Extremal problems for triple systems
- Extremal problems on set systems
- Extremal set systems with weakly restricted intersections
- Ryser's conjecture for \(t\)-intersecting hypergraphs
- Two remarks on eventown and oddtown problems
- A short note on supersaturation for oddtown and eventown
- On supersaturation for oddtown and eventown
- On set systems with strongly restricted intersections
This page was built for publication: Extremal systems with upper-bounded odd intersections
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1359376)
