Abrangendo árvore em um gráfico de conjuntos de interseção

Question

Considere $ n $ conjuntos, $ x_i $ , cada um tendo $ n $ elementos ou menos, desenhados entre um conjunto de no máximo $ m \ gt n $ elementos. Em outras palavras $$ \ forall i \ in [1 \ ldots n], ~ | x_i | \ le n ~ \ wedge \ \ esquerda | \ bigcock_ {i= 1} ^ n x_i \ direito | \ le m $$

Considere o gráfico completo $ g $ formado tomado a cada $ x_i $ como um nó, e Pesando cada borda $ (i, J) $ pelo cardeal da diferença simétrica $ x_i \ triangle x_j $ .

Um limite imediato no peso da árvore de abrangência mínima é $ \ mathcal {O} (n ^ 2) $ , já que cada borda é no máximo $ 2 N $ , mas podemos refinar isso para $ \ mathcal {O} (m) $ ?

? >

Para ilustração, considere $ 2 p $ conjuntos, $ p $ dos quais contêm os inteiros entre < span class="contêiner matemática"> $ 1 $ e $ P $ e $ p $ dos quais contêm os inteiros entre $ p + 1 $ e $ 2P $ . Uma árvore de abrangência mínima tem peso $ P $ Mas uma árvore mal escolhida neste gráfico teria peso $ (P-1) p $ . Intuitivamente, se houver apenas $ m $ valores para escolher, os conjuntos não podem ser diferentes uns dos outros.

editar: Colaborador Dmitry dá um bom contraexemplo abaixo no qual $ m $ é quase, mas não bastante $ n ^ 2 $ .

Uma contra-exemplo ou prova ainda seria de interesse no caso em que $ m=mathcal {o} (k n) $ . Pode o peso do spanning-tree ser vinculado por $ \ mathcal {o} (f (k) n) $ ? Por $ \ mathcal {o} (f (k) n \ log ^ c n) $ ?

Answer 1

Pergunta interessante.

a intuição certa provavelmente deve ser ao longo da diretriz que dois subconjuntos aleatórios de cardinalidade $ n $ desenhados de alguma $ cn $ elementos para alguma constante $ c $ diferem um do outro significativamente com uma probabilidade muito próxima de 1 e, portanto, o peso da árvore mínima de O gráfico $ g $ deve ser $ \ mathcal \ theta (n ^ 2) $ em média. Eu não posso provar que a diretriz está correta, no entanto.

Em vez disso, apresentarei uma série de exemplos. Mais especificamente, de alguma $ n $ (que pode ser grande arbitrário), existem $ n $ conjuntos , cada um com $ (N-1) / 2 $ elementos desenhados de um conjunto de $ n $ elementos , tal que a cardinalidade da diferença simétrica entre quaisquer dois conjuntos não é menor que $ (N-1) / 2 $ . Assim, o peso da árvore mínima de abrangência não é menor que $ (n-1) ^ 2/2=mathcal \ theta (n ^ 2) $ . .

---

.

Aqui está a construção, usando resíduo quadrático .

exemplo. deixe $ n= p $ ser um primo estranho. Deixe $ x_0 $ Seja o conjunto de todos os resíduos quadráticos não-zero da $ P $ entre 0 e < span class="contêiner matemática"> $ p-1 $ inclusive. Em outras palavras, $$ x_0= {0 \ le k \ lt p: \ left (\ frac {k} p \ direita)= 1 \} $$ Onde $ \ left (\ frac {\ cdot} p \ direita) $ é o símbolo legendário . Para $ 0 \ le i \ lt p $ , deixe $ x_i $ ser " $ x_0 $ mais $ i $ ", isto é, $$ x_i= {0 \ le k \ lt p: \ left (\ frac {ki} p \ direita)= 1 \}. $$ então $ | x_i |=frac {p -1} 2 $ para todos $ i $ e $ | x_i \ triangle x_j | \ GE \ frac {P-1} 2 $ para todos $ i \ Not= j $ .

prova : desde $ \ left (\ frac {\ cdot} p \ direita) $ é $ - 1 $ , $ 0 $ , ou $ 1 $ , temos $ 1+ \ left (\ frac {\ cdot} p \ direita) \ ge0 $ . Por isso, $$ \ begin {alinhado} & \ Quad \ Quad \ Sum_ {0 \ le k \ lt p} \ left (1+ \ left (\ frac {ki} p \ direita) \ direito) \ left (1+ \ left (\ frac {kj} p \certo, certo)\\ & \ GE \ sum_ {0 \ le k \ lt p \, \ land \, \ left (\ frac {ki} p \ direita)= 1 \, \ land \, \ left (\ frac {kj} p \ direita )= 1} \ \ left (1+ \ left (\ frac {ki} p \ direito) \ direito) \ left (1+ \ left (\ frac {kj} p \ direita) \ \\ &=sum_ {0 \ le k \ lt p \, \ land \, \ left (\ frac {ki} p \ direita)= 1 \, \ terra \, \ left (\ frac {kj} p \ direita)= 1} 4 \\ &= 4 \, | x_i \ cap x_j | \ fim {alinhado} $$ Por outro lado, temos $$ \ begin {alinhado} & \ Quad \ Quad \ Sum_ {0 \ le k \ lt p} \ left (1+ \ left (\ frac {ki} p \ direita) \ direito) \ left (1+ \ left (\ frac {kj} p \certo, certo)\\ &=sum_ {0 \ le k \ lt p} \ lt (1 + \ left (\ frac {ki} p \ direita) + \ left (\ frac {kj} p \ direita) + \ left (\ frac { ki} p \ direita) \ esquerda (\ frac {kj} p \ direita) \ direita) \\ &= p + 0 + 0 + \ sum_ {0 \ le k \ lt p} \ frac {k ^ 2- (i + j) k + ij} p \\ &= p-1 \ fim {alinhado} $$ Desde a $ p \ nmid (- (i + j)) ^ 2-4ij= (ij) ^ 2 $ , a última igualdade acima vem do caso de $ p \ nmid B ^ 2-4ac $ , teorema 1 no papel em certas quantias com expressões quadráticas envolvendo o símbolo de legendário . Então temos $ | x_i \ cap x_j | \ le \ frac {p-1} 4. $

Como $ | 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 \ marca de seleção $

---

.

Para as pessoas que apreciam exemplos concretos, aqui estão os conjuntos quando $ n= 17 $ , onde $ | x_i \ $ | triângulo x_j | \ G 8 $ . $$ \ begin {alinhado} X_ {0} &= {\ phantom {1} 1, \ phantom {1} 2, \ Phantom {1} 4, \ Phantom {1} 8, \ Phantom {1} 9, 13, 15, 16 \} \\ X_ {1} e= {\ Phantom {1} 2, \ Phantom {1} 3, \ Phantom {1} 5, \ Phantom {1} 9, 10, 14, 16, \ Phantom {1} 0 \} \\ X_ {2} e= {\ phantom {1} 3, \ phantom {1} 4, \ phantom {1} 6, 10, 11, 15, \ phantom {1} 0, \ phantom {1} 1} \\ X_ {3} e= {\ phantom {1} 4, \ Phantom {1} 5, \ Phantom {1} 7, 11, 12, 16, \ Phant

om {1} 1, \ phantom {1} 2 \} \\ X_ {4} e= {\ Phantom {1} 5, \ Phantom {1} 6, \ Phantom {1} 8, 12, 13, \ Phantom {1} 0, \ Phantom {1} 2, \ phantom { 1} 3 \} \\ X_ {5} e= {\ Phantom {1} 6, \ Phantom {1} 7, \ Phantom {1} 9, 13, 14, \ Phantom {1} 1, \ Phantom {1} 3, \ phantom { 1} 4 \} \\ X_ {6} e={\ phantom {1} 7, \ Phantom {1} 8, 10, 14, 15, \ Phantom {1} 2, \ phantom {1} 4, \ phantom {1} 5} \\ X_ {7} e={\ Phantom {1} 8, \ Phantom {1} 9, 11, 15, 16, \ Phantom {1} 3, \ phantom {1} 5, \ phantom {1} 6} \\ X_ {8} e= {\ Phantom {1} 9, 10, 12, 16, \ Phantom {1} 0, \ Phantom {1} 4, \ Phantom {1} 6, \ Phantom {1} 7} \\ X_ {9} e={10, 11, 13, \ Phantom {1} 0, \ Phantom {1} 1, \ Phantom {1} 5, \ Phantom {1} 7, \ Phantom {1} 8} \\ X_ {10} e={11, 12, 14, \ Phantom {1} 1, \ Phantom {1} 2, \ Phantom {1} 6, \ Phantom {1} 8, \ phantom {1} 9} \\ X_ {11} e={12, 13, 15, \ Phantom {1} 2, \ Phantom {1} 3, \ Phantom {1} 7, \ Phantom {1} 9, 10} \\ X_ {12} e={13, 14, 16, \ Phantom {1} 3, \ Phantom {1} 4, \ Phantom {1} 8, 10, 11} \\ X_ {13} e={14, 15, \ Phantom {1} 0, \ Phantom {1} 4, \ Phantom {1} 5, \ Phantom {1} 9, 11, 12 \} \\ X_ {14} e={15, 16, \ Phantom {1} 1, \ Phantom {1} 5, \ Phantom {1} 6, 10, 12, 13 \} \\ X_ {15} e={16, \ Phantom {1} 0, \ Phantom {1} 2, \ Phantom {1} 6, \ Phantom {1} 7, 11, 13, 14 \} \\ X_ {16} e= {\ Phantom {1} 0, \ Phantom {1} 1, \ Phantom {1} 3, \ Phantom {1} 7, \ Phantom {1} 8, 12, 14, 15} \\ \ fim {alinhado} $$

Answer 2

Você não pode. Considere os seguintes conjuntos para alguns $ k $ , com $ m= k ^ 2 $ (ambos são poderes de $ 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 $ .

Cada diferença simétrica é pelo menos $ \ FRAC K2 $ . Cada nível tem $ \ frac mk $ sets, e há $ 1 + \ log \ frac mk $ níveis . Portanto, existem $ \ frac mk (1 + \ log \ frac mk) $ conjuntos. Como cada conjunto deve ter cardinalidade no máximo o número de conjuntos, devemos ter $ k \ le \ frac mk (1 + \ log \ frac mk) $ , e é Satisfeito quando $ m= k ^ 2 $ .

O tamanho da árvore mínima de abrangência é pelo menos $ \ frac k 2 \ cdot \ frac mk (1 + \ log \ FRAC MK)=Ômega (m \ log m) $ .