Насколько велика дисперсия ширины дерева случайного графа в G (n, p)?

Я пытаюсь найти, насколько близки и , когда и является константой, не зависящей от n (поэтому ). Моя оценка такова: whp, но я не смог доказать это.E [ t w ( G ) ] G ∈ G ( n , p = c / n ) c > 1 E [ t w ( G ) ] = Θ ( n ) t w ( G ) ≤ E [ t w ( G ) ] + o ( n $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)$

Вам не нужно вычислять дисперсию, чтобы доказать концентрацию tw (G (n, p)) вокруг ее ожидания. Если два графа G 'и G отличаются на одну вершину, то их ширина дерева отличается не более чем на один. Вы можете использовать стандартный метод, неравенство Хоффдинга-Азумы, примененный к мартингалу экспозиции вершины, чтобы показать, например,

,$\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)$