1
$\begingroup$

Assume I have some array $a$ of length $n$.

If I place the elements contained in the array $a$ into a $\sqrt{n} \times \sqrt{n}$ matrix, then every row "intersects" with every column. That is, I cannot pick a row s.t. it will not intersect with all columns. In addition, I can "reach" each element in the matrix via a column and via a row vector. The row/column length is $\sqrt{n}$.

I'm not sure how to state this problem in more general terms or what would be a related field of research. Basically I am trying to find two sets $A$, $B$ of vectors/objects such that it holds that each element from $A$ intersects with all vectors from $B$ and in addition each element from $a$ should appear at least once in each set.

I was wondering whether the objects can be made even smaller by increasing the dimension to something bigger than 2. For instance, for dimension 3 I could have one set of planes and one set of orthogonal vectors. For these two sets it holds that every element from one set will intersect with every element from the other set. However, when placing the elements from the array $a$ into such a 3 dimensional cube, I would have planes that are composed of $\sqrt[3]{n} \cdot \sqrt[3]{n}$ elements and $\sqrt[3]{n}$ sized vectors. Here, the sum of two objects from these two sets is bigger than in the matrix example.

I would like to minimize the total size of objects, one from each set for a given dimension. What would be a related field of study to look at? Is dimension 2, i.e., the matrix already the best possible solution? If so, how would I show that?

|cite|improve this question
$\endgroup$

closed as off-topic by domotorp, Kaveh, David Eppstein, Mohammad Al-Turkistany, András Salamon Sep 7 '16 at 15:55

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – domotorp, David Eppstein, Mohammad Al-Turkistany, András Salamon
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ I don't understand your question. Do you want two partitions of an $n$ element set such that each part from one partition intersects each part from the other partition? Then $\sqrt n$ is indeed best possible. $\endgroup$ – domotorp Sep 1 '16 at 9:05
  • $\begingroup$ Yes that is pretty much it. How can I see that $\sqrt{n}$ is optimal? $\endgroup$ – simsim Sep 1 '16 at 9:06
  • 2
    $\begingroup$ This is really not a research level question. I recommend you ask on some other forum, or look here and figure it out: en.wikipedia.org/wiki/Young_tableau $\endgroup$ – domotorp Sep 1 '16 at 16:37
1
$\begingroup$

If I understand right, you are interested in finite projective planes. These are the maximum combinatoric set systems in which all sets intersect each other exactly once. To briefly answer your question, you can "improve" your construction by getting up to $\Omega(n)$ sets of size $\Omega(n^{1/2})$ and still enforcing the property that any two sets intersect on exactly one element (note: this only works for certain $n$, e.g. $n$ = square of a prime).

I assume you have some unstated restriction on your sets that rules out the construction $\{1, 2\}, \{1, 3\}, \{1, 4\} ...$ in which case your sets have size two but all pairs intersect on exactly one element?

|cite|improve this answer
$\endgroup$

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