A note on $k$-wise oddtown problems
Preprint
Abstract
For integers $2 \leq t \leq k$, we consider a collection of $k$ set families $\mathcal{A}_j: 1 \leq j \leq k$ where $\mathcal{A}_j = \{ A_{j,i} \subseteq [n] : 1 \leq i \leq m \}$ and $|A_{1, i_1} \cap \cdots \cap A_{k,i_k}|$ is even if and only if at least $t$ of the $i_j$ are distinct. In this paper, we prove that $m =O(n^{ 1/ \lfloor k/2 \rfloor})$ when $t=k$ and $m = O( n^{1/(t-1)})$ when $2t-2 \leq k$ and prove that both of these bounds are best possible. Specializing to the case where $\mathcal{A} = \mathcal{A}_1 = \cdots = \mathcal{A}_k$, we recover a variation of the classical oddtown problem.
Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Extremal Problems for Finite Sets2018
- Decomposing the complete r-graphJournal of Combinatorial Theory, Series A, 2018
- On decompositions of complete hypergraphsJournal of Combinatorial Theory, Series A, 2009
- Exact k-Wise Intersection TheoremsGraphs and Combinatorics, 2005
- Extremal set systems with restricted k-wise intersectionsJournal of Combinatorial Theory, Series A, 2004
- On k-wise set-intersections and k-wise Hamming-distancesJournal of Combinatorial Theory, Series A, 2002
- A Diagonal Form for the Incidence Matrices of t-Subsets vs.k-SubsetsEuropean Journal of Combinatorics, 1990
- On embedding graphs in squashed cubes1972
- On Subsets with Intersections of Even CardinalityCanadian Mathematical Bulletin, 1969