Conjetura de reconstrucción - Reconstruction conjecture

De manera informal, la conjetura de reconstrucción en la teoría de grafos dice que los gráficos están determinados únicamente por sus subgrafos. Se debe a Kelly y Ulam .

Declaraciones formales

Un gráfico y la plataforma asociada de subgráficos eliminados de un solo vértice. Tenga en cuenta que algunas de las tarjetas muestran gráficos isomorfos.

Dado un gráfico , un subgrafo de vértice eliminado es un subgráfico formado al eliminar exactamente un vértice de . Por definición, es un subgrafo inducido de . ${\ Displaystyle G = (V, E)}$${\ Displaystyle G}$${\ Displaystyle G}$${\ Displaystyle G}$

Para un gráfico , la plataforma de G , denotada , es el conjunto múltiple de clases de isomorfismo de todos los subgráficos de vértice eliminado . Cada gráfico de se llama tarjeta . Se dice que dos gráficos que tienen el mismo mazo son hipomórficos . ${\ Displaystyle G}$${\ Displaystyle D (G)}$${\ Displaystyle G}$${\ Displaystyle D (G)}$

Con estas definiciones, la conjetura se puede enunciar como:

• Conjetura de reconstrucción: dos gráficos hipomórficos cualesquiera en al menos tres vértices son isomorfos.

(El requisito de que los gráficos tengan al menos tres vértices es necesario porque ambos gráficos en dos vértices tienen los mismos mazos).

Harary sugirió una versión más fuerte de la conjetura:

• Conjetura de reconstrucción de conjuntos: dos gráficos cualesquiera en al menos cuatro vértices con los mismos conjuntos de subgráficos suprimidos por vértices son isomorfos.

Dado un gráfico , un subgrafo de borde eliminado es un subgrafo formado al eliminar exactamente un borde de . ${\ Displaystyle G = (V, E)}$${\ Displaystyle G}$${\ Displaystyle G}$

Para un gráfico , el tablero de borde de G , denotado , es el conjunto múltiple de todas las clases de isomorfismos de subgráficos con borde eliminado . Cada gráfico de se llama tarjeta de borde . ${\ Displaystyle G}$${\ displaystyle ED (G)}$${\ Displaystyle G}$${\ displaystyle ED (G)}$

• Conjetura de reconstrucción de bordes: (Harary, 1964) Dos gráficos cualesquiera con al menos cuatro bordes y que tengan las mismas cubiertas de bordes son isomorfos.

Propiedades reconocibles

En el contexto de la conjetura de la reconstrucción, una propiedad de un gráfico se llama reconocible si se puede determinar la propiedad a partir del tablero de un gráfico. Las siguientes propiedades de los gráficos son reconocibles:

• Orden del gráfico : se puede reconocer el orden de un gráfico , ya que el conjunto múltiple contiene cada subgráfico de creado al eliminar un vértice de . Por eso${\ Displaystyle G}$${\ Displaystyle | V (G) |}$${\ Displaystyle D (G)}$${\ Displaystyle D (G)}$${\ Displaystyle G}$${\ Displaystyle G}$${\ Displaystyle | V (G) | = | D (G) |}$
• Número de aristas del gráfico : el número de aristas en un gráfico con vértices es reconocible. Primero tenga en cuenta que cada borde de ocurre en miembros de . Esto es cierto por la definición de que asegura que cada borde se incluye cada vez que cada uno de los vértices con los que incide se incluye en un miembro de , por lo que se producirá un borde en cada miembro de excepto en los dos en los que sus extremos son eliminado. Por lo tanto, ¿ dónde está el número de aristas en el i- ésimo miembro de .${\ Displaystyle G}$${\ Displaystyle n}$${\ Displaystyle | E (G) |}$${\ Displaystyle G}$${\ Displaystyle n-2}$${\ Displaystyle D (G)}$${\ Displaystyle D (G)}$${\ Displaystyle D (G)}$${\ Displaystyle D (G)}$${\ Displaystyle | E (G) | = \ sum {\ frac {q_ {i}} {n-2}}}$${\ Displaystyle q_ {i}}$${\ Displaystyle D (G)}$
• Secuencia de grados: la secuencia de grados de un gráfico es reconocible porque el grado de cada vértice es reconocible. Para encontrar el grado de un vértice -el vértice ausente de la i º miembro del -, vamos a examinar el gráfico creado por eliminarlo, . Este gráfico contiene todas las aristas con las que no inciden , por lo que si es el número de aristas , entonces . Si podemos decir el grado de cada vértice en el gráfico, podemos decir la secuencia de grados del gráfico.${\ Displaystyle G}$${\ Displaystyle v_ {i}}$${\ Displaystyle D (G)}$${\ Displaystyle G_ {i}}$${\ Displaystyle v_ {i}}$${\ Displaystyle q_ {i}}$${\ Displaystyle G_ {i}}$${\ Displaystyle | E (G) | -q_ {i} = \ deg (v_ {i})}$
• (Vértice-) Conectividad : por definición, un gráfico está conectado al vértice cuando al eliminar cualquier vértice se crea un gráfico conectado al vértice ; por lo tanto, si cada tarjeta es un gráfico conectado al vértice, sabemos que el gráfico original estaba conectado al vértice. También podemos determinar si el gráfico original estaba conectado, ya que esto equivale a tener dos de los que están conectados.${\ Displaystyle n}$${\ Displaystyle n-1}$${\ Displaystyle n-1}$${\ Displaystyle n}$${\ Displaystyle G_ {i}}$
• Polinomio de Tutte
• Polinomio característico
• Planaridad
• Los tipos de árboles de expansión en un gráfico
• Polinomio cromático
• Ser un gráfico perfecto o un gráfico de intervalo , o ciertas otras subclases de gráficos perfectos.

Verificación

Tanto las conjeturas de reconstrucción como de reconstrucción de conjuntos han sido verificadas para todos los gráficos con un máximo de 11 vértices por Brendan McKay .

En sentido probabilístico, Béla Bollobás ha demostrado que casi todos los gráficos son reconstruibles. Esto significa que la probabilidad de que un gráfico de vértices elegido al azar no sea reconstruible va a 0 cuando va al infinito. De hecho, se demostró que no solo casi todas las gráficas son reconstruibles, sino que en realidad no es necesario todo el mazo para reconstruirlas; casi todas las gráficas tienen la propiedad de que existen tres cartas en su mazo que determinan de manera única el gráfico. ${\ Displaystyle n}$${\ Displaystyle n}$

Familias de gráficos reconstruibles

La conjetura se ha verificado para una serie de infinitas clases de gráficos (y, trivialmente, sus complementos).

• Gráficos regulares: los gráficos regulares se pueden reconstruir mediante la aplicación directa de algunos de los hechos que se pueden reconocer en el conjunto de un gráfico. Dado un gráfico regular y su mazo , podemos reconocer que el mazo es de un gráfico regular reconociendo su secuencia de grados. Examinemos ahora un miembro de la cubierta , . Este gráfico contiene cierto número de vértices con un grado de y vértices con un grado de . Podemos agregar un vértice a este gráfico y luego conectarlo a los vértices de grado para crear un gráfico regular que sea isomorfo al gráfico con el que comenzamos. Por lo tanto, todos los gráficos regulares son reconstruibles a partir de sus cubiertas. Un tipo particular de gráfico regular que es interesante es el gráfico completo.${\ Displaystyle n}$${\ Displaystyle G}$${\ Displaystyle D (G)}$${\ Displaystyle D (G)}$${\ Displaystyle G_ {i}}$${\ Displaystyle n}$${\ Displaystyle n}$${\ Displaystyle n-1}$${\ Displaystyle n}$${\ Displaystyle n-1}$${\ Displaystyle n}$
• Árboles
• Gráficos desconectados
• Gráficos de intervalo unitario
• Gráficos separables sin vértices finales
• Gráficos planos máximos
• Gráficos planos externos máximos
• Gráficos planos exteriores
• Bloques críticos

Reducción

La conjetura de la reconstrucción es cierta si todas las gráficas conectadas a 2 son reconstruibles.

Dualidad

La conjetura de reconstrucción de vértices obedece a la dualidad de que si se puede reconstruir a partir de su mazo de vértices , entonces su complemento se puede reconstruir de la siguiente manera: Comience con , tome el complemento de cada carta para obtener , use esto para reconstruir , luego tome el complemento de nuevo para conseguir . ${\ Displaystyle G}$${\ Displaystyle D (G)}$${\ Displaystyle G '}$${\ Displaystyle D (G ')}$${\ Displaystyle D (G ')}$${\ Displaystyle D (G)}$${\ Displaystyle G}$${\ Displaystyle G '}$

La reconstrucción de bordes no obedece a tal dualidad: de hecho, para algunas clases de grafos reconstruibles de bordes no se sabe si sus complementos son reconstruibles de bordes.

Otras estructuras

Se ha demostrado que, en general, lo siguiente no es reconstruible:

• Dígrafos : Se conocen infinitas familias de dígrafos no reconstruibles, incluidos los torneos (Stockmeyer) y los no torneos (Stockmeyer). Un torneo es reconstruible si no está fuertemente conectado. Se ha conjeturado una versión más débil de la conjetura de reconstrucción para los dígrafos, ver nueva conjetura de reconstrucción de dígrafos .
• Hypergraphs ( Kocay ).
• Gráficos infinitos . Sea T un árbol en un número infinito de vértices tal que cada vértice tiene un grado infinito, y sea n T la unión disjunta de n copias de T. Estos gráficos son hipomórficos y, por lo tanto, no son reconstruibles. Cada subgrafo con vértice eliminado de cualquiera de estos gráficos es isomorfo: todos son la unión disjunta de un número infinito de copias de T.
• Gráficos localmente finitos. La cuestión de la reconstrucción de árboles infinitos localmente finitos (la conjetura de Harary-Schwenk-Scott de 1972) fue un problema abierto de larga data hasta 2017, cuando Bowler et al.

Ver también

• Nueva conjetura de reconstrucción de dígrafos
• Simetría parcial

Otras lecturas

Para obtener más información sobre este tema, consulte la encuesta de Nash-Williams .

Referencias