¿Qué tan grande es la varianza del ancho de árbol de un gráfico aleatorio en G (n, p)?

Estoy tratando de encontrar qué tan cerca están realmente y , cuando y es una constante que no depende de n (entonces ). Mi estimación es que $tw(G)$ $E[tw(G)]$ $G \in G(n,p=c/n)$ $c>1$ $E[tw(G)] = \Theta(n)$ whp, pero no he podido probarlo. $tw(G) \leq E[tw(G)] + o(n)$

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

¿Cuál es la motivación para la pregunta? (es decir, ¿por qué está interesado en este problema?)

Kaveh

Bueno ... me preguntaba cuánto puede afectar el conocimiento de algunos bordes al ancho estimado del árbol (el conocimiento de la existencia de cada borde puede afectar el ancho del árbol como máximo uno), y eso me llevó a esta pregunta (que es mucho más interesante)

Kostas

En particular, esto tiene implicaciones para los límites superiores de conteo de modelos en el régimen satisfactorio para instancias aleatorias de SAT (y SAT cuántico), en la fase de gráficos aleatorios de Erdos-Renyi que tienen un gran componente conectado. En la medida en que nos interese el SAT aleatorio como un tema de la informática teórica, y también enfoques que involucren el ancho de árbol para limitar la complejidad de #SAT y problemas similares, esta pregunta está bien motivada.

Niel de Beaudrap

Respuestas:

No necesita calcular la varianza para probar la concentración de tw (G (n, p)) alrededor de su expectativa. Si dos gráficos G 'y G difieren en un vértice, entonces su ancho de árbol difiere en un máximo. Puede utilizar el método estándar, la desigualdad Hoeffding-Azuma aplicada a la martingala de exposición de vértices para mostrar, por ejemplo,

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

$t = n^{0.51}$

$G(n,p)$

Valentas
fuente