2021/09/21 by Jason O’Neill, O'Neill, Jason
Mathematics · #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Mathematical Dynamics and Fractals
paper · pdf · doi:10.48550/arxiv.2109.09925
openalex publication_date 2021/09/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a collection A of subsets of an n element set, let op(A) denote the number of distinct pairs A,B ∈ A for which |A ∩ B| is odd. For s ∈ \1,2\, we prove op(A) ≥ s ⋅ 2\lfloor n/2 \rfloor-1 for any collection A of 2\lfloor n/2 \rfloor+s even-sized subsets of an n element set. We also prove op(A) ≥ 3 for any collection A 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.