Extremal systems with upper-bounded odd intersections
type: Item
instance of: scholarly article
title: Extremal systems with upper-bounded odd intersections
zbMATH Open document ID: 0877.05001
DOI: 10.1007/BF03352996
author: Van Vu
published in: Graphs and Combinatorics
publication date: 1997-12-08T00:00:00Z
review text: 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}}\).
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 05D05
zbMATH DE Number: 1029269
zbMATH Keywords: extremal systems
zbMATH Keywords: \(s\)-family
reviewed by: Jack E. Graver
MaRDI profile type: Publication
cites work: On Subsets with Intersections of Even Cardinality
cites work: Boolean designs and self-dual matroids
cites work: Extremal set systems with weakly restricted intersections
full work available at URL: https://doi.org/10.1007/bf03352996
OpenAlex ID: W2039172146
Recommended article: Extremal set systems with weakly restricted intersections
Recommended article: Extremal \(n\)-systems of sets
Recommended article: Extremal Results for Algebraic Linear Interval Systems
Recommended article: Q5750908
Recommended article: Q4871772
Recommended article: Q3491615
Recommended article: Extremal set systems with restricted \(k\)-wise intersections.
Recommended article: Extremal problems for triple systems
Recommended article: Extremal problems on set systems
description: scientific article; zbMATH DE number 1029269