Realizable intersection graphs

32 Views Asked by At

Consider (finite) symmetric weighted graphs/matrices $\{\alpha_{ij}\}$ with $\alpha_{ij} \in \mathbb{N}_0$, $\alpha_{ij} = \alpha_{ji}$, and $\alpha_{ij} < \alpha_{ii} \neq 0$ for $i \neq j$ which are supposed to give the sizes of (maximal) sets $S_i$ and the sizes of intersections $S_i \cap S_j$ of a finite family of finite sets, where no set $S_j$ is a proper subset of any other set $S_i$.

My question is threefold:

  • Which graphs with the properties above are realizable by families of sets? How can one tell by just looking at the matrix entries? Call a matrix that is realizable by some family of sets its intersection matrix.

  • Given a graph/matrix realizable by some family of sets $\{S_i\}$, is this family of sets unique up to isomorphism? Or can there be non-isomorphic families of sets with the same matrix?

  • Which algorithms are there to calculate the size of the union $\bigcup_i S_i$ from a given intersection matrix? How hard is it to calculate it?

To give some examples find here the intersection graphs of some families of four four-element sets, together with the size of their union:

$\left|\begin{array}{cccc}4&0&0&0\\0&4&0&0\\0&0&4&0\\0&0&0&4\end{array}\right| = 16$

$\left|\begin{array}{cccc}4&1&1&1\\1&4&1&1\\1&1&4&1\\1&1&1&4\end{array}\right| = \left|\begin{array}{cccc}4&1&0&0\\1&4&1&0\\0&1&4&1\\0&0&1&4\end{array}\right| =13$

$\left|\begin{array}{cccc}4&1&0&1\\1&4&1&0\\0&1&4&1\\1&0&1&4\end{array}\right| = \left|\begin{array}{cccc}4&1&0&0\\1&4&2&0\\0&2&4&1\\0&0&1&4\end{array}\right| = 12$

$\left|\begin{array}{cccc}4&2&2&2\\2&4&2&2\\2&2&4&2\\2&2&2&4\end{array}\right| = \left|\begin{array}{cccc}4&2&0&0\\2&4&2&0\\0&2&4&2\\0&0&2&4\end{array}\right| =10$

$\left|\begin{array}{cccc}4&2&1&2\\2&4&2&1\\1&2&4&2\\2&1&2&4\end{array}\right| = 9$

$\left|\begin{array}{cccc}4&2&0&2\\2&4&2&0\\0&2&4&2\\2&0&2&4\end{array}\right| = 8 $

$\left|\begin{array}{cccc}4&3&3&3\\3&4&3&3\\3&3&4&3\\3&3&3&4\end{array}\right| = 7 $