I'm interested in the following:
Given a set $S_{n,k}$ of binary sequences of length $n$ with $k$ many 1-entries, what is the maximal size of a subset $S'_{k'}\subset S_{n,k}$ such that for every subset $T\subset S'_{k'}$ of size $k'$ there is no set of $k'$ many indices on which all elements of $T$ are $1$?
It seems to be quite a natural question to me, so i suppose there are some results. Unfortunately, I didn't find much on finite almost disjoint sets.
Thanks in advance!
So recast the problem as:
$Q(n,k,m,t):$ Given the family of all $k$ element subsets of $\{{1,\cdots,n\}}$, how large can a sub-family $\mathcal{F}$ be if we require that no $m$ of them have an intersection of size $t$?
Then your question is $Q(n,k,k',k')$. A very rough bound is that at the absolute largest we could imagine that every subset of of size $t$ is in $m-1$ members of $F$. If $N$ is the size of $F$ then counting in two ways all ways to select a member of $\mathcal{F}$ along with a further subset of size $t$ we have that $$N\binom{k}{t} \le (m-1)\binom{n}{t}$$ so $$N \le \frac{(m-1)\binom{n}{t}}{\binom{k}{t}} \tag{*}$$
It might be the case that that is not as crude as one might think in the sense that one can prove that there is for fixed $k,m,s$ always a family of size $N$ (rounded down to an integer) provided that $n$ is larger than some $n(k,m,s)$. However that could be a result of the form "there is at least one way to pick the family $\mathcal{F}$ which works" without any real guidance on how to get an actual specimen (nor an assurance that there are any examples with a compact description).
To get equality in $(*)$ requires the right hand side to be an integer (of course). Then $\mathcal{F}$ is called a $t$-design (with $\lambda=m-1$) and a Steiner system when $m=2$. A very exciting recent paper (link and description here) claims that this integrality condition is sufficient for existence, provided that $n$ is large enough.
Ahahahah. And I thought that I was the only one these days whose problems ALWAYS redirected to combinatorial designs.
Well, your problem is of the same kind, and I am sorry to say that the answers will be tricky.
Let us say that your set $S_{n,k}$ of binary sequences is all binary sequences of length $n$ with $k$ bits set to $1$ (i.e. all subsets of cardinality $k$ of a set of cardinality $n$). If you can answer your question with $k'=2$, then you can answer the following question:
"Does there exists a family of $k$-subsets of $\{1,...,n\}$ such that every pair of elements among $\{1,...,n\}$ is contained in exactly ONE set of this family ?"
This is the general problem of building BIBD. See this for example: http://en.wikipedia.org/wiki/Block_design#Definition_of_a_BIBD_.28or_2-design.29 http://en.wikipedia.org/wiki/Steiner_system http://en.wikipedia.org/wiki/Projective_plane#Finite_projective_planes
Solving this kind of problem exactly is probably hard, but it is somehow solved "asymptotically". I mean, when k is fixed and n gets large, and your family $S_{n,k}$ is the set of "all subsets of size $k$".
Your problem with $k\neq 2$ does not ring any bell, though. But it is pretty.
Nathann, who sympathizes with your problems.
