Intuición: transversal de ciclo impar en gráficos sin triángulo

Supongo que si es un gráfico simple sin triángulos, entonces hay un conjunto de a lo sumo bordes cuya eliminación destruye cada ciclo impar. $G$ $n^2/25$

Para obtener más información, consulte el artículo de 1988 de Erdös et al., Cómo hacer un gráfico bipartito .

Pregunta 1: ¿Es esta conjetura verdadera por su intuición?

Pregunta 2: ¿Cuál es la complejidad de contar el número de ciclos impares en un gráfico? ¿Hay algún algoritmo eficiente para hacer eso?

graph-theory Rupei Xu
fuente

Mi intuición dice que necesitas más que eso (considera la gráfica de 3 grupos de

vértices

modo que haya todos los bordes

, no lo pensé a través de). A

es una mucho más intuitivo unido. Pero mi intuición también dice: "Si Erdös lo dijo, tiene que ser cierto :)". Contar ciclos simples de longitud exactamente

es #W [1] -duro (con respecto a

n / 3

$n/3$

V_{1}, V_{2}, V_{3}

$V_1,V_2,V_3$

V_{1} \to V_{2} \to V_{3} \to V_{1}

$V_1 \to V_2 \to V_3 \to V_1$

n^{2} / 9

$n^2/9$

2 k + 1

$2k+1$

k

$k$ ), pero puede haber una manera más fácil de encontrar todos los ciclos impares.

@RB Esto ya debería ser una respuesta.

Yixin Cao

En realidad, ignoré por completo la parte sin triángulo: o. Para este tipo de gráficos, mi intuición dice que es verdad, y apretado (considere

para la igualdad de partición

V_{1} \to V_{2} \to V_{3} \to V_{4} \to V_{5} \to V_{1}

$V_1\to V_2\to V_3\to V_4\to V_5\to V_1$

V_{1}, . ., V_{5}

$V_1,..,V_5$

Querido Rupei, hay dos conjeturas bien conocidas de erdos en las que se supone que el gráfico propuesto por RB (y que quizás también tenías en mente) da el valor extremo. Uno está en el número máximo de pentágonos en un gráfico libre de triángulos con vértices 5n y el otro es igual a su conjetura sobre el número mínimo de aristas requerido para convertir un gráfico libre de triángulos en bipartito. Recuerdo vagamente que se hizo un progreso sustancial en la primera conjetura recientemente, pero tal vez mezcle las dos.

Gil Kalai

@GilKalai, muchas gracias por sus comentarios, querido profesor Kalai, encontré el siguiente documento que muestra los resultados que quiere decir: Simonovits, Miklós. "La influencia de Paul Erd en la teoría gráfica extrema". Las matemáticas de Paul Erdös II. Springer Berlin Heidelberg, 1997. 148-192.

Rupei Xu

Respuestas:

Mi intuición dice que probablemente sea cierto, y aquí hay un límite inferior coincidente (es decir, un gráfico del que debe eliminar al menos aristas para que se convierta en bipertita: $\frac{n^2}{25}$

, $G=(V_1\cup V_2\cup V_3\cup V_4\cup V_5, (V_1\times V_2) \cup (V_2\times V_3) \cup (V_3\times V_4) \cup (V_4\times V_5) \cup (V_5\times V_1))$ . $|V_1| = |V_2| = |V_3| = |V_4| = |V_5|$

Este gráfico es ciertamente libre de triángulos, pero si $x<\frac{n^2}{25}$ $C_5=v_1\to v_2\to v_3\to v_4\to v_5 \to v_1$ $v_1\in V_1, v_2\in V_2, v_3\in V_3, v_4\in V_4, v_5\in V_5$

$2k+1$ $\#W[1]-hard$ $k$ $n^{o(k)}$

$O^*(2^{O(k)})$

RB
fuente

O * (2^{O (k)})

$O∗(2^{O(k)})$

O^{*} (f (k))

$O^*(f(k))$

\tilde{O} (f (n))

$\widetilde O(f(n))$

O (f (n) p o l y l o g (f (n)))

$O(f(n)polylog(f(n)))$

n

$n$

O^{*}

$O^*$

Gracias por su referencia, es interesante ver una notación en diferentes significados.

Saeed

Un enfoque para probar su conjetura sería tratar de usar el lema de regularidad de Szemerédi , similar a la forma en que se prueba el lema de eliminación de triángulos (ver, por ejemplo, aquí ). Sin embargo, no sé si obtendrá las constantes correctas de este enfoque.

bola de masa de mobius
fuente

En el lema de regularidad de Szemerédi, generalmente supone una gran cantidad de particiones, el valor exacto de la partición no es fácil de obtener. Me pregunto que tal vez no funcione aquí.

Rupei Xu