Can we sometimes define the parity of a set?

Question

Suppose that ${n\choose k}, {n-1\choose k-1}, \ldots, {n-k+1\choose 1}$ are all even. (This happens for example if $k=2^\alpha-1$ and $n=2k$.) In this case, can we select ${n\choose k}/2$ sets of size $k$ from an $n$ element set such that any $i<k$ elements are contained in exactly ${n-i\choose k-i}/2$ of the selected sets?

This would be somekind of parity for the sets. If true, I am also interested in the natural generalization for $p\ne 2$ to define some $\!\!\mod p$ of a set.

The only nontrivial example that I know is for $k=3$ and $n=6$ which I have just learned from Douglas Zare who might have heard it from Robin Chapman, see his comment here.

Answer 1

I wish I had a real answer for you!

You are essentially interested in a tough conjecture of Hartmann, known as the "halving conjecture", which is promoted heavily by Reza Khosrovshahi. Actually, the conjecture is more general than what you are asking, since it concerns large sets of $t$-designs with arbitrary block size $k$, and I believe you have specialized to $t=k-1$. In other words, the more general conjecture asks if your condition holds for $i \le t$ when only the first $t+1$ of your binomial coefficients are even.

Here is the closest thing I know to an open-access survey: http://math.ipm.ac.ir/combin/publications/files/2009/PA0900076.pdf

See Section 6 in particular.

The halving conjecture is known to be true for $2$-designs. I haven't read the proof, but it is apparently nontrivial. In any case, this means your question has an affirmative answer for $k=3$ and all admissible $n$. For general $t$, quite a few partial results are known, such as product, puncturing, and complementing constructions. There are also important connections with null designs and trades.

I hope some of this helps for your particular application(s).

Answer 2

Here are some solutions for the largest possible set of conditions, $n=2k$.

Suppose $p$ is a prime that divides ${2k\choose k}, {2k-1\choose k-1}, \ldots, {k+1\choose 1}$. Then the selection conditions in your question (that is, $b={2k\choose k}/p$ blocks, with each element in $r={2k-1\choose k-1}/p$ of them, and each pair in ${2k-2\choose k-2}/p$, etc.) would create a $t$-$(2k,k,\frac{k+1}{p})$ design with $t=k-1$.

With $k=2$ we want a partition of a $4$ element set into two sets of size $2$, which certainly exists. The example you had in mind is $k=3$, and the one in my comment is $k=4$, so those exist.

When $k=5$, there are no primes dividing everything up to ${2k \choose k}$.

When $k=6$, we are looking for a $5-(12,6,1)$ design, which is uniquely the small Witt design.

When $k=7$, Donald Kreher and Stanislaw Radziszowski constructed a $6-(14,7,4)$ design in J. Combin. Theory (vol 43.2, Nov 1986) http://dx.doi.org/10.1016/0097-3165(86)90064-6

Finally, for $k\geq8$, Donald Kreher names the $7-(16,8,3)$ as the smallest unsettled $k-1$-design with $\lambda \neq 1$ in "Simple t-designs with large t: A survey" (which is an inaccesible preprint on his current homepage, but can be found here https://www.math.ucdavis.edu/~deloera/MISC/BIBLIOTECA/trunk/Moura/large_tdesign_survey.pdf), and notes that the only other known $k-1$-designs for $k \geq 8$ have $\lambda = k!^{2k-1}$, which is not the case here.

This still leaves open the cases where $n > 2k$, for example, the trivial design with $p=3$, $n=7$, $k=2$, or the $3-(13,4,2)$ design with $p=5$, which exists.