在相交的集合图表中的生成树

Question

考虑 $ n $ set， $ x_i $ ，每个都有 $ n $ 元素或更少，在大多数 $ m \ gt n $ 元素中。换句话说 $$ \ forall i \在[1 \ ldots n]，〜| x_i | \ le n〜\ wedge〜\ left | \ bigcup_ {i= 1} ^ n x_i \ leve | \ Le M $$

考虑完整图 $ g $ 通过占用每个 $ x_i $ 作为节点，称重每个边缘 $（i，j）$ 由对称差异的基数 $ x_i \ triangle x_j $ 。

在最小生成树的重量上的立即绑定为 $ \ mathcal {o}（n ^ 2）$ ，因为每个边缘最多 $ 2 $ ，但我们可以将其改进到 $ \ mathcal {o}（m）$ ？

用于说明，考虑 $ 2 p $ set， $ p $ ，其中包含<跨越类=“math-container”> $ 1 $ 和 $ p $ 和 $ p $ $ p + 1 $ 和 $ 2p $ 之间的整数。一个最小的生成树具有权重 $ p $ 但是这个图表上的一个糟糕的树是有权 $（p-1） p $ 。直观地，如果只有 $ m $ 作为选择的值，则该集不能彼此不同。

编辑： 贡献者DMITry在下面提供一个漂亮的反例，其中 $ m $ 几乎但不是完全 $ n ^ 2 $ 。

在 $ m=mathcal {o}（k n）$ 的情况下，对CounterSxample或证据仍然是感兴趣的。跨越树的权重由 $ \ mathcal {o}（f（k）n）$ ？通过 $ \ mathcal {o}（f（k）n \ log ^ c n）$ ？

Answer 1

有趣的问题。

正确的直觉可能是沿着指南的指南，其中两个随机子集的基本关系 $ n $ 从一些 $ cn $ 某些常量 $ c $ 彼此不同的概率非常接近1，因此，最小的生成树的重量图 $ g $ 应该是 $ \ mathcal \ theta（n ^ 2）$ 平均。但是，我无法证明这方面是正确的。

相反，我将呈现一系列这样的例子。更具体地说，来自一些 $ n $ （可以是任意大的），有 $ n $ 集，每个都有 $（n-1）/ 2 $ 从一组 $ n $ 元素，使得任何两组之间的对称差异的基数不小于 $（n-1）/ 2 $ 。因此，最小生成树的重量不小于 $（n-1）^ 2/2=mathcal \ theta（n ^ 2）$ 。

---

这里是施工，使用二次残留物。

示例。 let $ n= p $ 是一个奇数的素数。让 $ x_0 $ 是 $ p $ 之间的所有非零二次残基的集合0到< Span Class=“Math-Container”> $ P-1 $ 包容。换句话说， $$ x_0={0 \ Le k \ lt p：\ left（\ frac {k} p \ revion）= 1 \} $$ 其中 $ \ left（\ frac {\ cdot} p \ light）$ 是 legendre符号。对于 $ 0 \ le i \ lt p $ ，让 $ x_i $ be“ $ x_0 $ 加 $ i $ ”，即 $$ x_i={0 \ Le k \ lt p：\ left（\ frac {ki} p \ light）= 1 \}。$$ 然后 $ | x_i |=frac {p -1} 2 $ 对于所有 $ i $ 和 $ | x_i \ triangle x_j | \ ge \ frac {p-1} 2 $ 对于所有 $ i \ not= j $ 。

证明：由于 $ \ left（\ frac {\ cdot} p \ light）$ 是 $ - 1 $ ， $ 0 $ ，或 $ 1 $ ，我们有 $ 1+ \ left（\ frac {\ cdot} p \ lige）\ ge0 $ 。因此， $$ \ begin {aligned} ＆quad \ quad \ sum_ {0 \ le k \ lt p} \ left（left（\ frac {ki} p \右）\右）\ left（1+ \左（\ frac {kj} p \是的是的）\\ ＆\ ge \ sum_ {0 \ le k \ lt p \，\ land \，\ left（\ frac {ki} p \ light）= 1 \，\ land \，\ left（\ frac {kj} p \ ）= 1} \ left（左左（\ frac {ki} p \右）\右）\ left（1+ \ left（\ frac {kj} p \ offy）\ \\ ＆=sum_ {0 \ le k \ lt p \，\ land \，\ left（\ frac {ki} p \ light）= 1 \，\ land \，\ left（\ frac {kj} p \右）= 1} 4 \\ ＆= 4 \，| X_I \ CAP X_J | \结束{对齐} $$ 另一方面，我们有 $$ \ begin {aligned} ＆quad \ quad \ sum_ {0 \ le k \ lt p} \ left（left（\ frac {ki} p \右）\右）\ left（1+ \左（\ frac {kj} p \是的是的）\\ ＆=sum_ {0 \ le k \ lt p} \ left（1 + \ left（\ frac {ki} p \ light）+ \ left（\ frac {kj} p \ light）+ \ left（\ frac { ki} p \右）\ left（\ frac {kj} p \右）\右）\\ ＆= p + 0 + 0 + \ sum_ {0 \ le k \ lt p} \ frac {k ^ 2-（i + j）k + ij} p \\ ＆= p-1 \结束{对齐} $$ 由于<跨度类=“math-container”> $ p \ nmid（ - （i + j））^ 2-4ij=（ij）^ 2 $ ，上面的最后一个相等来自 $ p \ nmid b ^ 2-4ac $ ，纸张中的定理1 在某些涉及Legendre符号 的二次表达式上的某些和。所以我们有 $ | x_i \ cap x_j | \ le \ frac {p-1} 4。$

自 $ | x_i |= | x_j | 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 $

---

对于欣赏具体示例的人，这里是 $ n= 17 $ ，其中 $ | x_i \三角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，\ phant

OM {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 \} \\ \结束{对齐} $$

Answer 2

你不能。考虑以下设置某些 $ k $ ，带 $ m= k ^ 2 $ （它们都是 $ 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 $ < / span>
• $ \ {1,5,9，\ ldots，4k-3 \} $ ， $ \ {2 ，6,10，\ ldots，4k-2 \} $ $ \ ldots $ 。

每个对称差别至少是 $ \ frack2 $ 。 每个级别都有 $ \ frac mk $ 集合，并且有 $ 1 + \ log \ frac mk $ 级别。因此，存在 $ \ frac mk（1 + \ log \ frac mk）$ 集。 由于每个集合必须具有大多数集合的基数，因此我们必须具有 $ k \ le \ frac mk（1 + \ log \ frac mk）$ ，它是当 $ m= k ^ 2 $ 时，满意。

最小生成树的大小至少是 $ \ frac k 2 \ cdot \ frac mk（1 + \ log \ frac mk）=oomega（m \ log m）$ 。