Number of Edges in a Subset Graph of a Power Set

Question

Given a set $A$ of cardinality $n$, let $\mathbb{P}(A)$ be the power set of $A$. What is the number of edges of the intersection graph of the powerset of $A$. I.e how many pairs of sets $x,y$ have the property that $x,y \in \mathbb{P}(A) \land x \bigcap y \neq \varnothing$. Let's call this number $f(n)$. If $A = \{1\}$ then $f(1) = 0$. If $A = \{1,2\}$, then $f(2) = 2$ (since $\{1\},\{1,2\}$ and $\{2\},\{1,2\}$ are connected). If $A = \{1,2,3\}$, then $f(3) = 15$, see this to see why. I tried counting $f(4)$ and $f(5)$ and got $f(4) = 80, f(5) = 1652$. It seems like the formula is $$ \frac{1}{2}\left(4^n - 3^n - 2^n + 1\right) $$ But I can't see why. Any help or direction would be appreciated $:)$.

Answer 1

To specify an ordered pair $(x,y)$ with $x,y \in \mathbb P(A)$, we can go through all $n$ elements $i \in A$ and decide whether $i \in x$ and whether $i \in y$: $4$ choices at each step, for $4^n$ total.

To eventually get an edge out of such a pair $(x,y)$, we impose some additional restrictions (subtracting some terms from $4^n$):

1. We want $x \cap y \ne \varnothing$. So we eliminate $3^n$ pairs for which we never chose both $i \in x$ and $i \in y$ for the same $i$, because in that case $x$ and $y$ wouldn't actually intersect.
2. We want $x\ne y$. So we eliminate $2^n$ pairs for which we always either chose $i \in x, i \in y$ or $i \notin x, i \notin y$, because in that case $x$ and $y$ would be equal and we wouldn't get an edge of the graph.
3. There is one pair which violates both of the above restrictions: the pair $(\varnothing, \varnothing)$.

By the inclusion-exclusion principle, there are $4^n - 3^n - 2^n + 1$ pairs $(x,y)$ obeying both restrictions: pairs where $x \ne y$ and $x\cap y \ne \varnothing$.

Finally, we divide by $2$ because edges of the graph are unordered pairs $\{x,y\}$, getting $$\frac{4^n - 3^n - 2^n + 1}{2}.$$

Answer 2

Although not as conceptually clear as the other answer, another approach is to use induction. Suppose that the count is correct for $A = \{1,\ldots, n-1\}$ and consider the graph corresponding to $A \cup \{n\}$.

First, if $x, y \subseteq A$ were connected, then you get three edges in the graph for $A \cup \{n\}$, namely the ones between $(x, y)$, $(x \cup \{n\}, y)$, and $(x, y \cup \{n\})$. So we have $3 \times f(n-1)$ edges of this type. (We count $(x \cup \{n\}, y \cup \{n\})$ in the next step.)

You are adding $2^{n-1}$ new nodes, all of which contain $n$ and are therefore connected, for a total of $$ \binom{2^{n-1}}{2} = \frac{2^{n-1}(2^{n-1} - 1)}{2} = \frac12\left(4^{n-1} - 2^{n-1}\right) $$ edges.

Finally, for every $x \subseteq A$, there is an edge between $x$ and $x \cup \{n\}$, except when $x = \emptyset$, which gives another $2^{n-1} - 1$ edges.

Hence we get: $$ f(n) = 3\times \frac12 \times \left(4^{n-1} - 3^{n-1} - 2^{n-1} + 1\right) + \frac12\left(4^{n-1} - 2^{n-1}\right) + 2^{n-1} - 1, $$ and simply grouping powers of $2, 3, 4$ together shows that this is what we expected for $f(n)$.