A note on k-wise oddtown problems

Abstract: For integers

2 l e q t l e q k

, we consider a collection of

k

set families

m a t h c a l A_{j} : 1 l e q j l e q k

where

m a t h c a l A_{j} = A_{j, i} s u b s e t e q [n] : 1 l e q i l e q m

and

| A_{1, i_{1}} c a p c d o t s c a p 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 / l f l o o r k / 2 f l o o r})

when

t = k

and

m = O (n^{1 / (t - 1)})

when

2 t - 2 l e q k

and prove that both of these bounds are best possible. Specializing to the case where

m a t h c a l A = m a t h c a l A_{1} = c d o t s = m a t h c a l A_{k}

, we recover a variation of the classical oddtown problem.

Recommendations

Cites work

Cited in

(5)

This page was built for publication: A note on \(k\)-wise oddtown problems