32 votos

Hacer gráficos con un número impar de paseos de longitud entre dos vértices cualesquiera?

Dado 11 decimos que un gráfico GG es -bueno si para cada u,vGu,vG (no necesariamente distintos), el número de paseos de longitud de uu a vv es impar. Decimos que un gráfico GG es bueno si es -bueno para algunos 11 .

¿Existen los buenos gráficos? Para que quede claro, sólo hablo de grafos simples (que carecen de bucles y aristas múltiples).

Contexto: En el libro de Stanley sobre combinatoria algebraica, el ejercicio 1.13 trata de demostrar una interesante propiedad que se cumple para todos los grafos buenos. Un amigo mío me dijo que después de resolver el ejercicio, se dio cuenta de que no conocía ningún ejemplo de tales grafos. Yo también estoy perplejo sobre si pueden existir tales grafos.

Una búsqueda informática reveló que no existe ninguna con 77 o menos vértices. No tengo claro los detalles de la búsqueda, los hizo mi amigo.

37voto

Dean Hill Puntos 2006

Un gráfico sin bucles no puede ser bueno.

Supongamos lo contrario, que GG tienen nn vértices y ser bueno.

Dejemos que AA sea la matriz de adyacencia de GG , dejemos que λ1,,λnλ1,,λn sean sus valores propios sobre alguna extensión de F2F2 . Tenemos ni=1λi=trA=0ni=1λi=trA=0 .

Que AA es bueno significa que AA es una matriz todo-1 sobre F2F2 . Tiene rango 1, por lo que al menos n1n1 valores propios de AA son 0. Por otro lado, los valores propios de AA son λ1,,λnλ1,,λn . Por lo tanto, al menos n1n1 λiλi son cero, y como λi=0λi=0 , todos λiλi son 0. Por lo tanto AA es nilpotente. Como AA tiene rango 1, obtenemos A+1=0A+1=0 (de hecho, denota imA:=XimA:=X entonces dimX=1dimX=1 . Tenemos imA+1imA=XimA+1imA=X y también imA+1=AXimA+1=AX . Desde dimX=1dimX=1 , ya sea imA+1={0}imA+1={0} o AX=imA+1=XAX=imA+1=X En este último caso AA no es nilpotente ya que AkX=X{0}AkX=X{0} para todos k=0,1,2,k=0,1,2, ). Así que, AA=0AA=0 , lo que significa que la suma de las entradas en cada fila de AA es par, es decir, cada vértice de GG debe tener un grado parejo.

Ahora elige un vértice vv y que WW sea el conjunto de todos los paseos de longitud de vv a vv . La cardinalidad de WW es impar por hipótesis. La operación ρρ de invertir un paseo es una involución en WW por lo que el número de puntos fijos de ρρ es impar; estos puntos fijos consisten en paseos de la forma "tomar cualquier paseo de longitud /2/2 a partir de vv y luego volver sobre sus pasos hasta vv " (así en particular, debe ser par). Pero como cada vértice tiene grado par, en particular hay un número par de opciones para el último paso del paseo de longitud /2/2 por lo que el número total de paseos de longitud /2/2 debe ser uniforme. Esto es una contradicción.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X