¿Todo grafo bipartito con 512 aristas tiene un subgrafo inducido con 256 aristas?

Question

Supongamos que tenemos un grafo bipartito (simple) con $2^k$ bordes. ¿Es cierto que existe un subconjunto de vértices tal que su subgrafo inducido tiene exactamente $2^{k-1}$ ¿bordes?

Sé que la respuesta es no para los gráficos generales, ya que se puede tomar un $K_6$ más una arista disjunta. También sé que si no requerimos que el número de aristas sea una potencia de 2, la respuesta es de nuevo no como se muestra en un $K_{5,9}$ más una arista disjunta. Sospecho que la respuesta a mi pregunta también es no.

Observación: Una pregunta similar en la que el contraejemplo más pequeño tiene $181^2$ bordes'': http://www.math.bas.bg/serdica/1995/1995-219-230.pdf

Actualización: Sé que esto es válido para $k\le 3$ incluso para los gráficos generales.

Answer 1

No es una respuesta, pero me gusta esta pregunta, así que decidí documentar un callejón oscuro por el que pasé y que debería ser evitado (o más bien retocado).

Comienza el Callejón Oscuro.

Inicialmente, intenté obtener un contraejemplo a partir de consideraciones puramente teóricas de los números. Es decir, dejemos que $2^{2k-1}-1$ sea un primo de Mersenne. Sea $G$ sea el grafo formado por el grafo bipartito completo $K_{2^k+1, 2^k-1}$ junto con un borde aislado $e$ . Tenga en cuenta que $G$ contiene exactamente $2^{2k}$ bordes. Sea $H$ sea un subgrafo inducido de $G$ con exactamente $2^{2k-1}$ bordes. Tenga en cuenta que si $e \in H$ entonces $K_{2^k+1, 2^k-1}$ contiene un subgrafo inducido con exactamente $2^{2k-1}-1$ bordes. Pero esto es imposible ya que $2^{2k-1}-1$ es primo. Desgraciadamente, $K_{2^k+1, 2^k-1}$ tiene un subgrafo inducido con $2^{2k-1}$ bordes, tomando un subconjunto de tamaño $2^{k}$ del lado izquierdo y uno de tamaño $2^{k-1}$ desde el lado derecho. Este es otro ejemplo del comentario de Douglas Zare de no intentes hacer un contraejemplo que sea un grafo bipartito completo más algunas aristas.

Fin del Callejón Oscuro.

Answer 2

Es posible que haya metido la pata en mis cálculos, así que revísalo para estar seguro, pero creo que lo siguiente es un ejemplo de lo que buscas:

Comience con una copia de $K_{5,103}$ con vértices $v_1\ldots v_5,w_1\ldots w_{103}$ y eliminar los bordes $v_iw_i$ para $1\leq i\leq 5$ . Añade dos copias de $K_2$ para hacer un total de 512 bordes. Entonces, a menos que me equivoque en alguna parte de mi cálculo, ningún subgrafo inducido puede tener exactamente 256 aristas.

Encontré otros fallos cercanos (configuraciones iniciales similares que tenían exactamente 1 forma (hasta el reetiquetado de los vértices) de eliminar vértices dejando exactamente 256 aristas), así que no debería ser difícil modificar esta construcción para encontrar un ejemplo si resulta que el ejemplo anterior falla después de todo.

Answer 3

Es probable que Domotorp y ARupinski ya lo sepan, pero he pensado en dejar constancia de ello como una primera incursión para arrinconar un contraejemplo por un proceso de eliminación. No me molestaré en el caso general, sino que me centraré en la especificación de 256 de 512. Sea G la colección de todos los grafos bipartitos con 256 aristas.

Sólo consideraré los grafos bipartitos, y mi preocupación es el tamaño de los más pequeños conjunto de vértices y cuántas aristas pueden salir de él. Ciertamente, cualquier nodo con grado al menos 256 contendrá un subgrafo inducido de G. Además, dos nodos cualesquiera del conjunto pequeño con un grado combinado de 256 o más también contendrá un subgrafo de G. Es probable que haya una caracterización mejor que la siguiente: tres vértices cualesquiera con grado combinado de 383 y cualquier 4 vértices con grado combinado de 510 producirá un subgrafo de G. (Nótese que me estoy centrando en pequeños conjuntos de vértices independientes).

Por supuesto, podemos ignorar los vértices de grado 0. Si podemos caracterizar bien los grafos con, por ejemplo, un conjunto independiente de 3 vértices y un gran número de aristas (pero menos de 383) que no tienen un subgrafo de G, podríamos usar esto para clasificar con conjuntos independientes más grandes, hasta llegar a 23 vértices, la raíz cuadrada aproximada de 512. raíz cuadrada de 512.

EDITAR 2012.11.11 Lamentablemente, el análisis que se hace a continuación no es del todo correcto. Se puede encontrar un subgrafo de $K_{4,96}$ con $3*96=288$ aristas que no contiene ningún subgrafo inducido de G. Resulta que si hay suficientes aristas y los grados del conjunto mayor son cualquier cosa menos un subconjunto de 3 con a lo sumo un 2, entonces la conclusión es válida y de hecho $267$ los bordes son suficientes. Estoy seguro de que esta línea de investigación producirá algo útil, pero el tratamiento que sigue no es suficiente. En particular, ahora no estoy seguro de que haya un contraejemplo que no sea un subgrafo de, por ejemplo, $K_{7,n}$ para algunos $n$ . FIN DE LA EDICIÓN 2012.11.11

EDITAR 2012.11.09 Este problema no es exactamente uno sobre submultisets de enteros y la teoría de los números, pero si se toma esa perspectiva, se corta una amplia franja en el bosque de los grafos bipartitos de 512 aristas.

La razón principal por la que se necesitan 382 bordes procedentes de 3 puntos independientes mientras que se requieren menos de 270 puntos procedentes procedentes de 4 puntos independientes puede verse como algo puramente teórico: dado a=3 y b=127, no hay números enteros c y d tales que $0 \leq c \leq a$ y $0 \leq d \leq b$ y $cd=256$ . Así que $K_{3,127}$ es un grafo de 381 aristas que no tiene ningún subgrafo inducido que pertenezca a G. Sin embargo, la teoría de los números puede utilizarse para demostrar que 382 aristas de 3 puntos son suficientes, ya que podemos eliminar uno de los tres puntos y trabajar con los 2 restantes, o miramos el único punto con grado 128 y observamos que tiene suficientes vecinos de grado correcto que sólo necesitamos eliminar vecinos de grado 3 (o de menor grado si se nos acaban) para conseguir un subgrafo inducido de G.

El hecho de que 4 puntos requieran muchas menos aristas se debe a que se necesitan suficientes clases de residuos mod 4 para solucionar cualquier problema: o bien hay un $K_{4,64}$ subgrafo oculto, o hay al menos suficientes vértices de grado 1,2 y 3 para ajustar la suma mod 4. Como resultado, está claro que $252+ 4*3$ es suficiente para encontrar un subgrafo de G, así que seamos generosos y digamos que un grado combinado de 280 es suficiente para 4 vértices.

Ahora podemos aprovechar esa estimación y decir que para 5 (y 6 y 7) vértices que 350 (y 420 y 490) aristas respectivamente entre ellos son suficientes para encontrar un subgrafo de G, bien eliminando vecinos de los 5 vértices, bien eliminando el vértice entre los cinco con menor grado, reduciéndolo a un caso anterior.

Como 8 divide a 256, necesitamos encontrar un subgrafo de la forma $K_{8,32}$ o suficientes vértices de menor grado para terminar el trabajo. Las estimaciones aproximadas dan 304 como grado combinado suficiente, que ahora podemos aprovechar para decir que no se encontrarán contraejemplos en 512 aristas de 13 vértices.

Probablemente podamos ampliarlo analizando más el caso de 12 vértices, pero lo dejaré para más adelante. Ahora sospecho que domotorp no conseguirá su contraejemplo para grafos bipartitos con $2^n$ bordes para $n \lt 10$ . FIN DE EDICIÓN 2012.11.09

Gerhard "Inching His Way Toward Bounty" Paseman, 2012.11.08

Answer 4

Aunque esto no es una respuesta completa, hay suficientes elementos en este post que creo que alguien puede utilizar para mostrar a domotorp donde no buscar un contraejemplo. También quiero separarlo del desorden marginalmente útil en el otro post mío. Recordemos que estoy centrado en mostrar que todo grafo bipartito H con exactamente 512 aristas tiene un subconjunto de vértices que da lugar a G, nuestro objetivo de un subgrafo inducido de H con exactamente 256 aristas.

Un hecho útil: si n es una potencia prima, si M es un subconjunto de divisores propios positivos de n con suma igual a n, entonces hay un submultiplano M' de M con suma kn/p, donde k y p son enteros positivos, k es menor que p, y p es el primo que divide a n. Un corolario de este hecho es que cualquier número positivo de vértices independientes cuya suma de grados sea al menos 256 y cuyos vecinos tengan grados que sean precisamente potencias de 2 tendrá un subgrafo inducido G precisamente en ese conjunto de vértices independientes. Edición: para que el corolario se lea correctamente, supongamos un subgrafo H de K_a,b con suma de grados de los vértices de a al menos 256 y los grados de los vértices de b son potencias adecuadas de 2. Entonces el subgrafo G de K_a,b' existe como subgrafo inducido de H. Fin de la edición.

Del corolario obtenemos que domotorp no encontrará ningún gráfico contraejemplo H que sea subgráfico de K_a,b para a=1 o a=2. Además, para a=3 o 4, no habrá ningún contraejemplo porque al menos dos de los vértices independientes de H tendrán una suma de grados de al menos 256. Sin embargo, quiero refinar un poco el caso de a=4.

Sea J un subgrafo de K_4,b con un número de aristas n = 256 + 3k para algún número entero no negativo k. Entonces J también tiene un subgrafo inducido G: eliminar los b vértices de grado 3 y todo lo que sea necesario para alcanzar el número de aristas objetivo. Si J tiene una gran cantidad de grados, elimine los vértices de grado 1,2 o 4 hasta n=256+3k como se ha indicado anteriormente. En caso contrario, J tiene menos de 264 aristas o bien los vértices b tienen todos grado 3, con una excepción como máximo que debe ser de grado 2. Ahora, de los cuatro vértices independientes, se elimina de J el vértice que tiene el grado más pequeño. El resultado tendrá menos de 260 aristas, o tendrá un vértice b de grado 1 o al menos dos de grado 2, o se eliminará una sola arista dejando un subgrafo K_3,b. En el primer caso, J tiene menos de 350 aristas, en el segundo y tercer caso se obtiene el grafo meta G, y en el último caso no se obtiene G a menos que b sea al menos 128. El resultado es que si J tiene más de 381 aristas, tendrá un grafo objetivo G como subgrafo inducido.

Me preocupó el caso a=4 a trozos por un par de razones: una es establecer que cualquier H que sea un subgrafo de K_5,b tendrá cuatro de los cinco vértices independientes con suma de grado superior a 400 (y por tanto no será un contraejemplo), y dos es poner un tope de tipo Rube Goldberg en este post para a=6. Esta idea de la prueba es bonita, y podría ser extensible, pero voy a dar a otros la oportunidad de hacerlo.

Sea H un subgrafo con 512 aristas y sea un subgrafo de K_6,b. Obsérvese que si dos de los seis vértices independientes tienen una suma de grados de al menos 256 o alguno de esos seis tiene un grado inferior a 12, puedo pasar a los casos para a=2 y a=5 y afirmar que existe un G objetivo.

Ahora encontraré cuatro de los seis vértices y espero que haya una G que utilice esos vértices. Obsérvese que podemos suponer que los cuatro vértices tienen una suma de grados de al menos 256.

Primero considera las sumas de grado de los seis mod 3. La suma de las sumas es 2=512 mod 3. Supongamos que dos de los grados mod 3 son 2. Entonces los cuatro restantes tienen sumas de grados iguales mod 3 a 256, así que puedo usar eso para producir G. Así que supongamos que a lo sumo uno de los seis grados es 2 mod 3. Entonces si hay otro grado no nulo mod 3, hay al menos uno que es cero mod 3, y esos dos los excluyo de los cuatro para obtener otra suma de grados igual mod 3 a 256, y de nuevo obtengo G. El caso restante que se resuelve bien es si ninguno es 2 mod 3, y de nuevo puedo encontrar G.

El último caso es que uno de los seis vértices tiene grado 2 mod 3, y todos los demás son 0 mod 3. De los 5 restantes, puedo intentar elegir algún subconjunto de 4 y esperar que ese subgrafo no caiga en el caso de que el subconjunto de b vértices me frustre por tener todos tres o todos tres y uno dos. Pero si tengo tan mala suerte, entonces tomo los 5 vértices para obtener un conjunto de grados con algunos cuatros o algunos unos, así como algunos treses o doses (recuerda que al menos 12 grados se incrementarán, aunque algunos de ellos podrían haber empezado en 0). Así puedo garantizar un conjunto de grados que permita la composición que quiero, y obtener mi gráfico G de premio.

¡Las cosas que hago por la recompensa!

Gerhard "Wait Till You See Seven" Paseman, 2012.11.14

Answer 5

Tienes razón querido domotorp,

Supongamos que el segundo mayor valor propio del grafo bipartito $G$ es uno, es decir $\lambda_2=1$ . En este caso, $G$ pertenecen al tipo finito, (hay un número infinito de tales grafos), grafos bipartitos. Con algunos cálculos, podemos ver que su conjetura es cierta para este tipo de grafos. Además, podemos decir más, si utilizamos algunas otras técnicas espectrales.

La referencia del papel:

Petrovic M., On graphs with exactly one eigenvalue less than -1, J. Combin. Theory Ser. B 52 (1991), 102-112.