Qual é o tamanho da variação da largura de árvore de um gráfico aleatório em G (n, p)?

Eu estou tentando encontrar o quão perto e realmente são, quando e é uma constante, não dependendo de n (assim ). Minha estimativa é que whp, mas não consegui provar isso. $tw(G)$ $E[tw(G)]$ $G \in G(n,p=c/n)$ $c>1$ $E[tw(G)] = \Theta(n)$ $tw(G) \leq E[tw(G)] + o(n)$

graph-theory co.combinatorics treewidth random-graphs Kostas
fonte

Qual é a motivação para a pergunta? (ou seja, por que está interessado neste problema?)

Kaveh

Bem ... eu queria saber o quanto o conhecimento de algumas arestas pode afetar a largura de árvore estimada (o conhecimento da existência de cada aresta pode afetar a largura de árvore em no máximo uma), e isso me levou a essa pergunta (que é muito mais interessante)

Kostas

Em particular, isso tem implicações para os limites superiores da contagem de modelos no regime satisfatório para instâncias aleatórias de SAT (e quantum-SAT), na fase de gráficos aleatórios de Erdos-Renyi com um grande componente conectado. Na medida em que nos preocupamos com o SAT aleatório como um tópico da ciência da computação teórica, e também com abordagens envolvendo largura de árvore para limitar a complexidade do #SAT e problemas semelhantes, essa pergunta é bem motivada.

Niel de Beaudrap

Respostas:

Você não precisa calcular a variação para provar a concentração de tw (G (n, p)) em torno de sua expectativa. Se dois gráficos G 'e G diferem em um vértice, sua largura de árvore difere em no máximo um. Você pode usar o método padrão, a desigualdade de Hoeffding-Azuma, aplicada à martingale de exposição a vértices para mostrar, por exemplo,

$\mathbb{P}( | tw(G(n,p)) - \mathbb{E} tw(G(n,p))| > t) \le 3 e^{- t^2/(2 n)}$ ,

então a probabilidade acima tende a 0, se, digamos . $t = n^{0.51}$

O método foi aplicado pela primeira vez para provar a concentração para o número cromático de . Veja B. Bollobás, gráficos aleatórios. Springer New York, 1998, página 298. $G(n,p)$

Valentas
fonte