Extremal set systems with weakly restricted intersections

DOI10.1007/S004939970008MaRDI QIDQ1977442zbMATH OpenOpenAlexFDO

Authors Van Vu

Publication date 14 May 2000

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s004939970008

zbMATH Keywords

extremal setsrestricted intersections

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Extremal set theory (05D05)

Review text

In this excellent paper extremal set systems with intersections of restricted cardinality are studied. If, say, each intersection has even cardinality then a linear algebraic tool (linear independence of the characteristic vectors of the subsets) gives an upper bound for the number of subsets. If, for each \(i\), the cardinality constraints for \(A_i \cap A_j\) can be violated by at most \(s\) subsets of form \(A_j\) then this ``\(s\)-weak version of the problem can still be handled by additional tools (from extremal graph theory, for instance) if \(s\) is relatively small. The author gives a tight upper bound for the weak version of the ``odd town problem (odd subsets with even intersections); for the weak version of the non-uniform Fisher inequality (leading to a new, extremal set theoretic characterization of Hadamard's matrices); and for the weak version of the ``even town problem (even intersections only). This latter leads to results in case of restricted multi-intersections as well.

Recommendations

• Extremal set systems with restricted \(k\)-wise intersections.
• Extremal systems with upper-bounded odd intersections
• scientific article; zbMATH DE number 863493
• Exact \(k\)-wise intersection theorems
• scientific article; zbMATH DE number 4164914

Cited in

(16)

• Extremal systems with upper-bounded odd intersections
• Extremal set systems with restricted \(k\)-wise intersections.
• On \(k\)-wise set-intersections and \(k\)-wise Hamming-distances
• Flattening rank and its combinatorial applications
• Ryser's conjecture for \(t\)-intersecting hypergraphs
• A strengthened inequality of Alon-Babai-Suzuki's conjecture on set systems with restricted intersections modulo \(p\)
• Topological designs
• Two remarks on eventown and oddtown problems
• Almost-Fisher families
• Almost-Fisher families
• Set-systems with restricted multiple intersections
• On maximal weakly separated set-systems
• A short note on supersaturation for oddtown and eventown
• On supersaturation for oddtown and eventown
• On set systems with strongly restricted intersections
• q-analogues of Fisher's inequality and oddtown theorem

This page was built for publication: Extremal set systems with weakly restricted intersections

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