I am trying to formalise a problem that I have. I have two different ideas but I don't know which one of them is the most suitable to solve my problem.
Let's say I have $m$ different sets $X_i$, with $i=1,\dots m$ and $n$ elements. Each element lies in $k$ of these sets. Now I want to find out, for at least one element, in which sets it lays.
I am given $|X_i|$ for all $i=1,\dots, m$ and $|X_i \cap X_j|$ for all $i\not=j$, $i,j=1,\dots, m$.
How big can $m$ and $n$ be at most to be able to find a solution?
My other idea to formalise this problem is representing it using matrices Let the columns represent the sets, and the lines an element. If the element lies in a set, we put $1$ in the matrix, otherwise $0$. \begin{pmatrix} a_{11}&a_{12}&\dots&a_{1m}\\ a_{21}&a_{22}&\dots&a_{2m}\\ \vdots&\vdots&\dots&\vdots\\ a_{n1}&a_{n2}&\dots&a_{nm} \end{pmatrix} We are given the following information:
(i) we know that $k$ values per line are $1$ and the other $m-k$ are $0$; so
$\sum\limits_{j=1}^m a_{ij}=k$ for all $i=1,\dots, n.$
(ii) the values $x_j=\sum\limits_{i=1}^{n}a_{ij}$ for all $j$
and
(ii) the values $y_{js}=\sum\limits_{i=1}^{n}(a_{ij}\cdot a_{is})$ for all $j=1,\dots m-1$ and $s=(j+1),\cdots m$.
Given this information, we want to find the values for all $a_{i1}, a_{i2}, \dots, a_{im}$ for at least one $i\in \{1,\dots,n\}$ (all the values of at least one line). Or more precisely, we want to find $t_1,\dots, t_k$ such that $a_{it_1}=a_{it_2}=\dots=a_{it_k}=1$. (We do not need to know in which line exactly, we are only looking for the right columns to be $1$.)
How big can $n$ and $m$ maximal be to be able to find at all the values in at least one line of the matrix?
I do not know how to include the fact that I do not need to calculate all unknown values of the matrix, but only the entries for one line; and also that the order of the lines is not important.
I calculated the number of equations I have given. This is $n$ equations from (i), $ml$ equations from (ii) and $ml\frac{(ml-1)}{2}$ from (iii). So we have $n+ml\frac{(ml+1)}{2}$ equations. But since we do not need to find all entries, how many unknown variables do I really have?
Could anyone give me a hint of how this can be calculated and if my idea makes sense? I have tried to understand better looking at examples, but I didn't manage to formalise my ideas.
Example: let our matrix be \begin{pmatrix} 1&1&0&1\\ 1&1&1&0 \end{pmatrix} We are given \begin{align*} a_{11}+a_{21}=2& &a_{11}*a_{12}&+a_{21}*a_{22}=2\\ a_{12}+a_{22}=2& &a_{11}*a_{13}&+a_{21}*a_{23}=1\\ a_{13}+a_{23}=1& &a_{11}*a_{14}&+a_{21}*a_{24}=1\\ a_{14}+a_{24}=1& &a_{12}*a_{13}&+a_{22}*a_{23}=1\\ &&a_{12}*a_{14}&+a_{22}*a_{24}=1\\ &&a_{13}*a_{14}&+a_{23}*a_{24}=0 \end{align*} We can solve this easily to get $$a_{11}=a_{21}=a_{12}=a_{22}=1$$ and $$(a_{13}=a_{24}=0\text{ and }a_{14}=a_{23}=1)\text{ or }(a_{13}=a_{24}=1\text{ and }a_{14}=a_{23}=0).$$
(edit) maybe I should specify that it is enough for our purpose to know the structure of a line, at not in which line we find this structure. So with the above example, knowing that we have one line of the form $$a_{i1}=a_{i2}=a_{i3}=1 \text{ and } a_{i4}=0$$ is good enough. In this example we know moreover that $$a_{i1}=a_{i2}=a_{i4}=1 \text{ and } a_{i3}=0.$$