P-gráfico de los elementos de la partición de 100 en común relación de divisibilidad

Question

Teniendo en cuenta un conjunto múltiple de enteros positivos, su gráfico de P es el gráfico loopless cuyo vértice situado consiste de los enteros, dos de los cuales se unen por un borde si tienen un divisor común mayor que 1, es decir, no son relativamente privilegiadas.

El gráfico de P de una partición de cierto misterio de 100 tiene 10 vértices y aristas de 42. Me han dicho que no hay otra particion de 100 tiene exactamente el mismo P-gráfico. ¿Qué es esta partición misterio de 100?

Answer 1

Deje $G$ el gráfico deseado. Podemos considerar las posibles $\overline{G}$ en 10 vértices con 3 bordes. Hay 5 de ellos: $(7K_1, K_3)$, $(6K_1,K_{1, 3})$, $(6K_1, P_4)$, $(5K_1, P_2, P_3)$ y $(4K_1, 3P_2)$.

Si $G \cong \overline{(6K_1, P_4)}$ luego de partición no es única: $$100 = 2 + 20 + 15 + 3 + 6 + 6 + 12 + 12 + 12 + 12\\ = 2 + 20 + 15 + 3 + 6 + 6 + 6 + 12 + 12 + 18\\ = 2 + 20 + 15 + 3 + 6 + 6 + 6 + 6 + 12 + 24\\ = 2 + 20 + 15 + 3 + 6 + 6 + 6 + 6 + 18 + 18\\ = 2 + 20 + 15 + 3 + 6 + 6 + 6 + 6 + 6 + 30.$$ Hay exactamente 3 pares de relativamente números primos: $2$ y $15$, $2$ y $3$, $20$ y $3$, porque en los últimos $6$ números son divisibles por $2$ y $3$, $2$ y $20$ son divisibles por $2$, $3$ y $15$ son divisibles por $3$, $15$ y $20$ son divisibles por $5$.

El mismo para $G \cong \overline{6K_1, K_{1, 3}}$: $$100 = 5 + 6 + 12 + 12 + 10 + 10 + 10 + 10 + 10 + 15\\ = 5 + 6 + 6 + 18 + 10 + 10 + 10 + 10 + 10 + 15.$$

Si $G \cong \overline{(7K_1, K_3)}$, en cada vértice de $7K_1$ debe tener al menos $3$ primer divisores de tener borde con cada uno de los 3 pares no adyacentes vértices de $K_3$. Por lo tanto, no se $7$ números de partición que por lo menos $30$ cada uno. Entonces es imposible obtener la suma de $100$.

Si $G \cong \overline{(4K_1, 3P_2)}$ al menos $4$ de los vértices de $3P_2$ debe tener al menos $3$ factores primos de cada uno de los (diferentes para cada vértice) por lo tanto el máximo de ellos es, al menos,$3 \cdot 5 \cdot 7 = 105 > 100$. Por lo que este gráfico da ninguna partición.

Si $G \cong \overline{(5K_1, P_2, P_3)}$, hay una partición: $$100 = 10 + 10 + 21 + 14 + 15 + 6 + 6 + 6 + 6 + 6.$$ Para probar que es único para este gráfico démonos cuenta de que cada vértice debe tener al menos $2$ factores primos y hay, al menos, $4$ factores primos en total. Como se muestra más arriba es posible tomar $2, 3, 5$ $7$ como factores primos y $5$ $6$ parejas de valores para los vértices. También es fácil ver que de esta manera da el mínimo de la suma de los valores. Si tomamos otro de los factores primos o más, a continuación, $2$ factores primos de, al menos, $1$ vértice, a continuación, tenemos aún mayor suma. Por lo tanto, esta partición es único por su P-graph.

Answer 2

Supuse que no hay repeticiones en la partición y no auto-bucles en el gráfico y se encontró ninguno que cumplieron con los requisitos.

Si las repeticiones son permitidos en la partición hay 2977866 las posibles particiones de longitud de 10 a explorar. Independientemente, entonces se convierte en claro si dos vértices con el mismo entero debe estar vinculado.

Independientemente, aquí es un gráfico con la repetición en la partición de tener $\{15,12,10,10,10,10,10,10,8,5\}$ tener 42 bordes:

La 10a, 10b, etc. distinguir los nodos que se corresponden con el elemento repetido 10.

Aquí está el gráfico encontrado por Smylic:

Bernardo muestra que no son isomorfos.