Spanning tree in a graph of intersecting sets

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 $mathcalTheta(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=mathcalTheta(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={0le klt p: left(frac {k}pright)=1}$$ where $left(frac{cdot}pright)$ is the Legendre symbol. For $0le ilt p$, let $X_i$ be "$X_0$ plus $i$", i.e., $$X_i={0le klt p: left(frac {k-i}pright)=1}.$$ Then $|X_i|=frac{p-1}2$ for all $i$ and $|X_i triangle X_j|ge frac{p-1}2$ for all $inot=j$.

Proof: Since $left(frac{cdot}pright)$ is either $-1$, $0$, or $1$, we have $1+left(frac{cdot}pright)ge0$. Hence, $$begin{aligned} &quadquad sum_{0le klt p}left(1+left(frac {k-i}pright)right)left(1+left(frac {k-j}pright)right)\ &gesum_{0le klt p,land,left(frac {k-i}pright)=1,land, left(frac {k-j}pright)=1}left(1+left(frac {k-i}pright)right)left(1+left(frac {k-j}pright)right)\ &=sum_{0le klt p,land,left(frac {k-i}pright)=1,land, left(frac {k-j}pright)=1}4\ &=4,|X_icap X_j| end{aligned}$$ On the other hand, we have $$begin{aligned} &quadquad sum_{0le klt p}left(1+left(frac {k-i}pright)right)left(1+left(frac {k-j}pright)right)\ &=sum_{0le klt p}left(1 + left(frac {k-i}pright) + left(frac {k-j}pright)+ left(frac {k-i}pright)left(frac {k-j}pright)right)\ &=p + 0 + 0 + sum_{0le klt p} frac {k^2-(i+j)k+ij}p\ &=p-1 end{aligned}$$ Since $pnmid(-(i+j))^2-4ij=(i-j)^2$, the last equality above comes from the case of $pnmid b^2-4ac$, theorem 1 in the paper On Certain Sums with Quadratic Expressions Involving the Legendre Symbol. So we have $|X_icap 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_icap X_j|ge frac{p-1}2.$ $quadcheckmark$

---

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}$$

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)$.