Intuição: Ciclo ímpar transversal em gráficos sem triângulo

Conjeturo que, se é um gráfico livre de triângulo simples, em seguida, existe um conjunto de, no máximo, bordas cuja eliminação destrói cada ciclo estranho. $G$ $n^2/25$

Para obter mais informações, consulte o artigo de Erdös et al., 1988, Como fazer um gráfico bipartido .

Pergunta 1: Essa conjectura é verdadeira por sua intuição?

Pergunta 2: Qual é a complexidade de contar o número de ciclos ímpares em um gráfico? Existe algum algoritmo eficiente para fazer isso?

graph-theory Rupei Xu
fonte

Minha intuição diz que você precisa de mais do que isso (considere o gráfico de 3 grupos de

vértices

modo que haja todas as arestas

, não pensei através). Um

é um tanto mais intuitiva ligado. Mas minha intuição também diz: "Se Erdös disse isso, tem que ser verdade :)". Contar ciclos simples de comprimento exatamente

é #W [1] -hard (em relação 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$ ), mas pode haver uma maneira mais fácil de encontrar todos os ciclos ímpares.

@RB Isso já deve ser uma resposta.

Yixin Cao

Na verdade, eu ignorei completamente a parte sem triângulo: o. Para tais gráficos, minha intuição diz que é verdade, e apertado (considere

para a igualdade de partição

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$

Caro Rupei, existem duas conjecturas conhecidas de erdos, nas quais o gráfico proposto por RB (e talvez você também tenha em mente) deve fornecer o valor extremo. Um é o número máximo de pentágonos em gráficos sem triângulo com 5n vértices e o outro é o mesmo que a sua conjectura no número mínimo de arestas necessárias para transformar um gráfico sem triângulo em bipartido. Lembro-me vagamente de que houve um progresso substancial na primeira conjectura recentemente, mas talvez eu misture as duas.

Gil Kalai

@ GilKalai, muito obrigado por seus comentários, prezado professor Kalai, encontrei o seguinte artigo que mostra os resultados que você quer dizer: Simonovits, Miklós. "A influência de Paul Erdős na teoria dos grafos extremais." A matemática de Paul Erdös II. Springer Berlin Heidelberg, 1997. 148-192.

Rupei Xu

Respostas:

Minha intuição diz que provavelmente é verdade, e aqui está um limite inferior correspondente (ou seja, um gráfico do qual você deve excluir pelo menos arestas para se tornar 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 é certamente livre de triângulo, mas se $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
fonte

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^*$

Obrigado pela sua referência, é interessante ver uma notação em diferentes significados.

Saeed

Uma abordagem para provar sua conjectura seria tentar usar o lema de regularidade de Szemerédi , semelhante à maneira como o lema de remoção de triângulo é comprovado (veja, por exemplo, aqui ). Não sei se você obterá as constantes corretas dessa abordagem.

bolinho de massa mobius
fonte

No lema de regularidade do Szemerédi, normalmente ele assume um grande número de partições, o valor exato da partição não é fácil de obter. Gostaria de saber que talvez não funcione aqui.

Rupei Xu 15/05