<p>If I understand right, you are interested in <a href="https://en.wikipedia.org/wiki/Projective_plane#Finite_projective_planes" rel="nofollow">finite projective planes</a>.  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).</p>

<p>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?</p>

CC BY-SA 3.0
2016-09-01T20:40:38.420Z
More generally, [combinatorial designs](https://en.wikipedia.org/wiki/Combinatorial_design) are possibly relevant.
Klaus Draeger
CC BY-SA 3.0
2016-09-01T17:23:25.497Z
2016-09-01T17:42:58.707Z
2016-09-01T17:42:58.707Z
GMB
<p>Assume I have some array $a$ of length $n$.</p>

<p>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 <em>all</em> 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}$. </p>

<p>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$ <em>and</em> in addition each element from $a$ should appear at least once in each set. </p>

<p>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.</p>

<p>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?</p>

CC BY-SA 3.0
2016-09-01T09:05:17.847Z
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.
domotorp
CC BY-SA 3.0
2016-09-01T09:06:33.730Z
Yes that is pretty much it. How can I see that $\sqrt{n}$ is optimal?
Cryptonaut
CC BY-SA 3.0
2016-09-01T16:37:51.230Z
This is really not a research level question. I recommend you ask on some other forum, or look here and figure it out: https://en.wikipedia.org/wiki/Young_tableau
domotorp
<computational-geometry>
Finding sets of heavily intersecting objects, while minimizing their size
Cryptonaut
# Finding sets of heavily intersecting objects, while minimizing their size

(Asked by: username_0 on 2016-08-31)

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?

**Tags:** computational-geometry

> **Comments:**
> **username_1**: 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.  
> **username_0**: Yes that is pretty much it. How can I see that $\sqrt{n}$ is optimal?  
> **username_1**: This is really not a research level question. I recommend you ask on some other forum, or look here and figure it out: https://en.wikipedia.org/wiki/Young_tableau  

---

## 1 answers

### Answer by username_2 on 2016-09-01. Score: 1

If I understand right, you are interested in [finite projective planes](https://en.wikipedia.org/wiki/Projective_plane#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?

> **Comments:**
> **username_3**: More generally, [combinatorial designs](https://en.wikipedia.org/wiki/Combinatorial_design) are possibly relevant.  

---

