3
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you very much. I'm trying to understand the paper right now. It all looks very interesting! $\endgroup$ – Sebastian Mueller Mar 26 '14 at 8:57
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.