A short note on supersaturation for oddtown and eventown

DOI10.1016/J.DAM.2023.03.003zbMATH Open1520.05095arXiv2109.09925OpenAlexW4327905042MaRDI QIDQ6157418FDOQ6157418

Authors: Jason O'Neill 

Publication date: 11 May 2023

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: Given a collection $mathcalA$ of subsets of an $n$ element set, let $extop(mathcalA)$ denote the number of distinct pairs $A,BinmathcalA$ for which $|AcapB|$ is odd. For $sin1,2$, we prove $extop(mathcalA)geqscdot{2}^{lfloorn/2floor-1}$ for any collection $mathcalA$ of $2^{lfloorn/2floor}+s$ even-sized subsets of an $n$ element set. We also prove $extop(mathcalA)geq3$ for any collection $mathcalA$ of $n+1$ odd-sized subsets of an $n$ element set that. Moreover, we show that both of these results are best possible. We then consider larger collections of odd-sized and even-sized sets respectively and explore the connection to minimizing the number of pairwise intersections of size exactly $k-2$ amongst collections of size $k$ subsets from an $n$ element set.

Full work available at URL: https://arxiv.org/abs/2109.09925

Recommendations

• Two remarks on eventown and oddtown problems
• Specified intersections
• Extremal systems with upper-bounded odd intersections
• Minimum saturated families of sets
• A note on \(k\)-wise oddtown problems

zbMATH Keywords

intersecting set familiessupersaturationlinear algebra method

Mathematics Subject Classification ID

Extremal set theory (05D05)

Cites Work

• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Forbidding just one intersection
• The minimum number of disjoint pairs in set systems and related problems
• On functions of strength t
• Sperner's Theorem and a Problem of Erdős, Katona and Kleitman
• Set systems with few disjoint pairs
• Title not available (Why is that?)
• Boolean designs and self-dual matroids
• On Subsets with Intersections of Even Cardinality
• On subsets with cardinalities of intersections divisible by a fixed integer
• Extremal set systems with weakly restricted intersections
• Extremal Problems for Finite Sets
• Exact \(k\)-wise intersection theorems
• Extremal systems with upper-bounded odd intersections
• Kleitman's conjecture about families of given size minimizing the number of \(k\)-chains
• Lovász theta approach to eventown problem
• Two Remarks on Eventown and Oddtown Problems
• A note on \(k\)-wise oddtown problems

This page was built for publication: A short note on supersaturation for oddtown and eventown

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