Let $C_1, \ldots, C_K$ be the collection of $K$ disjoint subsets (I'll call them components) of $\mathbb R^d$ so that:
- Each $C_i$ is connected and open.
- $\cup_i cl(C_i) = \mathbb R^d$, where $cl$ is the closure.
- You can assume that $C_i$ is not "weird". To be more specific, in my case, the boundaries between the components are roots of a finite number of polynomials.
I want to know the upper bound on the number of neighboring pairs of components. I call $C_i$ and $C_j$ neighbors if, informally, their boundaries have a non-trivial intersection. More formally, the ($(d-1)$-dimensional Lebesgue) measure of $cl(C_i) \cap cl(C_j)$ is not zero (again, you can assume that everything is well-behaved and there are no weird measure-theoretical problems).
In a 2-dimensional case, I could use the Euler's Formula for planar graphs (with vertices representing the components and edges representing the neighbors). I expect the answer to be $O(dK)$, which I would be totally happy about.
I suspect that there is a theorem that directly answers the question, but can't find it.
P.S.: don't know which tags to use.
For $d > 2$, the answer is $\binom K 2$. There is no dependence on $d$. In three dimensions or higher you can always arrange for the $K$ sets to be in pair-wise mutual contact. Consider $K-1$ balls, then run small tubes from each running between each pair. In three dimensions, they can move around each other. Connect each tube to one of the spheres, and leave it disconnected only by the sphere surface on the other. The final $C_K$ is the complement of the closure of their union.
For $d = 1$, the answer is clearly $K - 1$. It is only for $d=2$ that the question is hard.
[Edit:]
First we can do a standard conversion of the problem: Pick a point $v_i$ in each $C_i$, and for every pair of neighbors $C_i, C_j$ pick a point $p_{ij} = p_{ji}$ with a neighborhood intersecting only the closures of those two cells (whose existence I'll take as the definition of $\text{cl}(C_i) \cap \text{cl}(C_j)$ being non-trivial). Since the $C_i$ are connected, paths exist inside them connecting the $v_i$ to each $p_{ij}$. I'll gloss over the technical argument that the paths can be chosen not to cross each other. By pasting this path with the path from $v_j$ to $p_{ij}$, we get a path connecting $v_i$ to $v_j$, converting the original problem of the number of pairs of neighboring cells in a collection of $K$ cells to a problem of the maximum number of edges possible in a planar graph of $K$ vertices.
Because of how it was constructed, this graph is connected, has no loops (edges connecting a vertex to itself), and at most one edge between any two vertices. Thus if there are $3$ or more vertices, the faces each have at least three edges bounding them. If there are faces with four or more edges, then another edge could be added connecting vertices on this face that are not adjacent. Thus for a graph with the maximal number of edges, all the faces must be triangular.
Let $V, E, F$ be the number of vertices, edges, and faces. So $V+F-E = 2$. Since each edge borders two faces, $2E = 3F$, so $E = 3V - 6$.
Therefore when $d = 2, K > 2$, the maximum number of pairs of neighboring cells is $$3(K-2)$$.