Minimum number of switches required to connect $N$ nodes into any possible partition? Suppose I have a box with $N$ "pins", and I want to build a network of wires inside the box consisting of simple on/off switches that allow me to connect pins into any partition (set of disjoint subsets whose union is the set of $N$ pins) via some state of the switches.
For example, here is a box with $N=3$ pins.

There are 5 possible partitions, i.e. configurations of how the wires can be connected into disjoint sets:
{{1},{2},{3}}
{{1,2},{3}}
{{1,3},{2}}
{{2,3},{1}}
{{1,2,3}}


*

*The first partition has no connected pins, so all switches should be open (off).

*The last partition connects all pins together, so at least 2 switches should be closed (on) to connect all pins together.

*The middle three partitions connect two pins, so the switch connecting them should be closed.


For general $N$, what is the minimum number of switches needed to configure all possible partitions of pins?
An obvious upper bound is $N(N-1)/2$, the number of edges in a complete graph. But is it possible to build a network inside the box that doesn't require every node to be connected directly to every other node?
A lower bound is $\lceil \log_2(B_N) \rceil$ where $B_N$ is the Bell number, due to the pigeonhole principle of $2^k$ switch states needed for $B_N$ partitions of $N$ pins.
 A: As noted by Bob Krueger, your lower bound is $\Omega(n \log n)$. Here is a construction to achieve that bound $O(n \log n)$. The idea is to lay the pins on a vertical line, and then somehow sort the pins up to the point where pins that must be connected together are consecutive. From there $n-1$ links are sufficient. Let's see what I mean precisely.
Start from a sorting network on $n$ wires. For each comparator in the sorting network, replace it by this gadget:

and add links between consecutive output vertices of the network.
For instance, on 8 wires we would get, starting from a bitonic sorter:

where the pins are the squared nodes.
Why does it work? Consider a partition $\mathcal{P}$ of $\{1,2,\ldots,n\}$. Choose a total order on $\{1,2,\ldots,n\}$ such that elements in a part of $\mathcal{P}$ are consecutive in that order. We can represent that order as a permutation $\sigma$ where $\sigma(i)$ is the position of $i$ in that order. Then consider which links are active for the sorting network applied on $\sigma$, and take the corresponding edges in our construction, together with edges on the last column to encode the partition. For instance, if $\mathcal{P} = \{ \{1,8\}, \{2,5,6,7\}, \{3,4\} \}$, with compatible order $1 < 8 < 2 < 5 < 6 < 7 < 8 < 3 < 4$, we get $\sigma = (1 3 7 8 4 5 6 2)$, and take the red set to connect the pins as requested by the partition:

Now it is sufficient to take a $O(n \log n)$-size sorting network, and we know that those exists (see the wikipedia article on sorting networks), as the number of vertices and edges is linear in the size of the sorting network. Notice that we don't really need something as powerful as a sorting network: in a sorting network, comparators swap elements based on their relative value, while we have the choice whether to swap or not to swap independently of the values. Hence there may be a smart easy construction for a network allowing any permutation in $\Theta(n \log n)$.
A: Let the number of pins be $n$. I can improve the trivial upper bound from $\binom{n}{2} \approx n^2/2$ to around $n^2/4$. Note that if there are no internal nodes, then we must have a direct connection between every pair of nodes, so we should exploit the internal nodes in some way. The trivial lower bound you give is on the order of $n\log n$, and I no opinion on what the growth rate of the minimum number of switches should be.
Now for the construction(s). Create $\lfloor n/2 \rfloor$ internal nodes -- call these 'meeting rooms.' Connect every pin to every meeting room. This network has the partition property since in any partition there are at most $\lfloor n/2 \rfloor$ parts of size greater than $1$, and for each such part we can link them into a meeting room. This uses $n\lfloor n/2 \rfloor$ switches, which is the same or slightly worse than the trivial construction, but we can quickly improve this construction.
Take $k$ pins and attach them to only one meeting room (in total being $k$ distinct meeting rooms), and attach the remaining pins to all the meeting rooms. Among the $k$ pins form another network with the partition property. Then for any partition of the $n$ pins, we can first connect the correct pins together from the special $k$ pins, then we can link those $k$ pins into a meeting room to connect them to the correct ones of the remaining $n-k$ pins. Using a complete graph on the $k$ pins, we optimize $k$ to be around $n/2$ and get around $\frac{3}{8} n^2$ switches. Applying this construction recursively yields at best around $\frac{1}{4} n^2$ switches.
