# Spanning tree in a graph of intersecting sets

Consider $$n$$ sets, $$X_i$$, each having $$n$$ elements or fewer, drawn among a set of at most $$m \gt n$$ elements. In other words $$\forall i \in [1 \ldots n],~|X_i| \le n~\wedge~\left|\bigcup_{i=1}^n X_i\right| \le m$$

Consider the complete graph $$G$$ formed by taking every $$X_i$$ as a node, and weighing every edge $$(i,j)$$ by the cardinal of the symmetric difference $$X_i \triangle X_j$$.

An immediate bound on the weight of the minimal spanning tree is $$\mathcal{O}(n^2)$$, since each edge is at most $$2 n$$, but can we refine this to $$\mathcal{O}(m)$$?

For illustration, consider $$2 p$$ sets, $$p$$ of which contain the integers between $$1$$ and $$p$$ and $$p$$ of which contain the integers of between $$p+1$$ and $$2p$$. A minimal spanning tree has weight $$p$$ but a poorly chose tree on this graph would have weight $$(p-1)p$$. Intuitively, if there are only $$m$$ values to chose from, the sets can't all be that different from one another.

EDIT: Contributor Dmitry gives a nice counterexample below in which $$m$$ is nearly but not quite $$n^2$$.

A counterexample or proof would still be of interest in the case where $$m = \mathcal{O}(k n)$$. Can the weight of spanning-tree be bound by $$\mathcal{O}(f(k) n)$$? By $$\mathcal{O}(f(k) n \log^c n)$$?

• The tight bound is, I believe, $\mathcal O(n^2)$. Jul 25, 2020 at 5:13
• Do you have an example of a sequence of graphs where m = o(n^2) and the minimum spanning tree has weight O(n^2)? Or, even stronger, m = O(n) and weight O(n^2) Jul 25, 2020 at 5:32
• Yes. I am writing a proof. It may take a while. Jul 25, 2020 at 5:38
• Neat! Is the proof only for m = o(n^2) or does it also work for m = O(n)? Jul 25, 2020 at 5:43
• Yes. $\phantom{}$ Jul 25, 2020 at 14:49

Interesting question.

The right intuition should probably be along the guideline that two random subsets of cardinality $$n$$ drawn from some $$cn$$ elements for some constant $$c$$ differ from each other significantly with a probability very close to 1 and, hence, the weight of the minimum spanning tree of the graph $$G$$ should be $$\mathcal\Theta(n^2)$$ on average. I cannot prove that guideline is correct, however.

Instead, I will present one series of such examples. More specifically, from some $$n$$ (that can be arbitrary large), there are $$n$$ sets, each having $$(n-1)/2$$ elements drawn from a set of $$n$$ elements, such that the cardinality of the symmetric difference between any two sets is no less than $$(n-1)/2$$. So the weight of the minimum spanning tree is no less than $$(n-1)^2/2=\mathcal\Theta(n^2)$$.

Here is the construction, using quadratic residue.

Example. Let $$n=p$$ be an odd prime. Let $$X_0$$ be the set of all non-zero quadratic residues of $$p$$ between 0 and $$p-1$$ inclusive. In other words, $$X_0=\{0\le k\lt p: \left(\frac {k}p\right)=1\}$$ where $$\left(\frac{\cdot}p\right)$$ is the Legendre symbol. For $$0\le i\lt p$$, let $$X_i$$ be "$$X_0$$ plus $$i$$", i.e., $$X_i=\{0\le k\lt p: \left(\frac {k-i}p\right)=1\}.$$ Then $$|X_i|=\frac{p-1}2$$ for all $$i$$ and $$|X_i \triangle X_j|\ge \frac{p-1}2$$ for all $$i\not=j$$.

Proof: Since $$\left(\frac{\cdot}p\right)$$ is either $$-1$$, $$0$$, or $$1$$, we have $$1+\left(\frac{\cdot}p\right)\ge0$$. Hence, \begin{aligned} &\quad\quad \sum_{0\le k\lt p}\left(1+\left(\frac {k-i}p\right)\right)\left(1+\left(\frac {k-j}p\right)\right)\\ &\ge\sum_{0\le k\lt p\,\land\,\left(\frac {k-i}p\right)=1\,\land\, \left(\frac {k-j}p\right)=1}\left(1+\left(\frac {k-i}p\right)\right)\left(1+\left(\frac {k-j}p\right)\right)\\ &=\sum_{0\le k\lt p\,\land\,\left(\frac {k-i}p\right)=1\,\land\, \left(\frac {k-j}p\right)=1}4\\ &=4\,|X_i\cap X_j| \end{aligned} On the other hand, we have \begin{aligned} &\quad\quad \sum_{0\le k\lt p}\left(1+\left(\frac {k-i}p\right)\right)\left(1+\left(\frac {k-j}p\right)\right)\\ &=\sum_{0\le k\lt p}\left(1 + \left(\frac {k-i}p\right) + \left(\frac {k-j}p\right)+ \left(\frac {k-i}p\right)\left(\frac {k-j}p\right)\right)\\ &=p + 0 + 0 + \sum_{0\le k\lt p} \frac {k^2-(i+j)k+ij}p\\ &=p-1 \end{aligned} Since $$p\nmid(-(i+j))^2-4ij=(i-j)^2$$, the last equality above comes from the case of $$p\nmid b^2-4ac$$, theorem 1 in the paper On Certain Sums with Quadratic Expressions Involving the Legendre Symbol. So we have $$|X_i\cap X_j|\le \frac{p-1}4.$$

Since $$|X_i|=|X_j|=\frac{p-1}2$$, $$\ |X_i \triangle X_j|=|X_i|+|X_j|-2|X_i\cap X_j|\ge \frac{p-1}2.$$ $$\quad\checkmark$$

For people who appreciate concrete examples, here are the sets when $$n=17$$, where $$|X_i \triangle X_j|\ge 8$$. \begin{aligned} X_{0}&=\{\phantom{1}1, \phantom{1}2, \phantom{1}4, \phantom{1}8, \phantom{1}9, 13, 15, 16 \}\\ X_{1}&=\{\phantom{1}2, \phantom{1}3, \phantom{1}5, \phantom{1}9, 10, 14, 16, \phantom{1}0 \}\\ X_{2}&=\{\phantom{1}3, \phantom{1}4, \phantom{1}6, 10, 11, 15, \phantom{1}0, \phantom{1}1 \}\\ X_{3}&=\{\phantom{1}4, \phantom{1}5, \phantom{1}7, 11, 12, 16, \phantom{1}1, \phantom{1}2 \}\\ X_{4}&=\{\phantom{1}5, \phantom{1}6, \phantom{1}8, 12, 13, \phantom{1}0, \phantom{1}2, \phantom{1}3 \}\\ X_{5}&=\{\phantom{1}6, \phantom{1}7, \phantom{1}9, 13, 14, \phantom{1}1, \phantom{1}3, \phantom{1}4 \}\\ X_{6}&=\{\phantom{1}7, \phantom{1}8, 10, 14, 15, \phantom{1}2, \phantom{1}4, \phantom{1}5 \}\\ X_{7}&=\{\phantom{1}8, \phantom{1}9, 11, 15, 16, \phantom{1}3, \phantom{1}5, \phantom{1}6 \}\\ X_{8}&=\{\phantom{1}9, 10, 12, 16, \phantom{1}0, \phantom{1}4, \phantom{1}6, \phantom{1}7 \}\\ X_{9}&=\{10, 11, 13, \phantom{1}0, \phantom{1}1, \phantom{1}5, \phantom{1}7, \phantom{1}8 \}\\ X_{10}&=\{11, 12, 14, \phantom{1}1, \phantom{1}2, \phantom{1}6, \phantom{1}8, \phantom{1}9 \}\\ X_{11}&=\{12, 13, 15, \phantom{1}2, \phantom{1}3, \phantom{1}7, \phantom{1}9, 10 \}\\ X_{12}&=\{13, 14, 16, \phantom{1}3, \phantom{1}4, \phantom{1}8, 10, 11 \}\\ X_{13}&=\{14, 15, \phantom{1}0, \phantom{1}4, \phantom{1}5, \phantom{1}9, 11, 12 \}\\ X_{14}&=\{15, 16, \phantom{1}1, \phantom{1}5, \phantom{1}6, 10, 12, 13 \}\\ X_{15}&=\{16, \phantom{1}0, \phantom{1}2, \phantom{1}6, \phantom{1}7, 11, 13, 14 \}\\ X_{16}&=\{\phantom{1}0, \phantom{1}1, \phantom{1}3, \phantom{1}7, \phantom{1}8, 12, 14, 15 \}\\ \end{aligned}

• So, essentially, the sets can all be that different. What led you to quadratic residues as a way to construct this example? Jul 25, 2020 at 14:52
• The right intuition should be that the symmetric difference are $O(n)$ with probability asymptotically very very close to 1 if all sets are $O(n)$ uniformly. So $\mathcal\Theta(n^2)$ is likely to be tight. I tried to find $\mathcal\Theta(n^2)$ examples by various means. Finally I started to check quadratic residues because of my vague memory of their "even distribution". It worked. Jul 25, 2020 at 15:03
• Ah I see. It should basically work with anything random enough. Empirically, I checked with gray codes and it works, might be possible to prove that one too. For n = 2^r pick set x[ j ] = { ((i << 1) ^ i + j) & (n -1) for i = 1..2^(r-1) } and the symmetric difference is at least 2^(r-2). Jul 26, 2020 at 4:20

You can't. Consider the following sets for some $$k$$, with $$m=k^2$$ (they both are powers of $$2$$):

• $$\{1..k\}$$, $$\{k+1..2k\}$$, $$\ldots$$, $$\{m-k+1..m\}$$
• $$\{1, 3, 5, \ldots, 2k-1\}$$, $$\{2, 4, 6, \ldots, 2k\}$$, $$\{2k+1, 2k+3, \ldots, 4k - 1\}$$, $$\{2k+2, 2k+4, \ldots, 4k\}$$, $$\ldots$$
• $$\{1, 5, 9, \ldots, 4k - 3\}$$, $$\{2, 6, 10, \ldots, 4k-2\}$$ $$\ldots$$.

Each symmetric difference is at least $$\frac k2$$. Each level has $$\frac mk$$ sets, and there are $$1 + \log \frac mk$$ levels. Therefore, there are $$\frac mk(1 + \log \frac mk)$$ sets. Since each set must have cardinality at most the number of sets, we must have $$k \le \frac mk (1 + \log \frac mk)$$, and it's satisfied when $$m = k^2$$.

The size of the minimum spanning tree is at least $$\frac k 2 \cdot \frac mk (1 + \log \frac mk) = \Omega(m \log m)$$.

• The difference between two nodes is at most 2n and there are at most n-1 edges so I don't see how you can get more than O(n²). Jul 23, 2020 at 4:00
• But I didn't? $n = k (1 + \log k)$. You were asking if we can get $O(m)$, and the answer is no.
– user114966
Jul 23, 2020 at 4:17
• Ah I see. If that's OK with you I'd like to amend the original question to narrow it down a bit. Jul 23, 2020 at 6:29
• I don't understand why there aren't $n = 2k^2 - k$ sets in your example. Say $k = 8$ for instance, the first level would have 8 sets, then 16 .. then 64. That's $120 = 2 \times 64 - 8$ no? Jul 23, 2020 at 6:44
• Sure, it's your question:) Each level consists of disjoint sets of size $k$. So the number of sets at each level is always $\frac mk$
– user114966
Jul 23, 2020 at 6:46