OurBigBook About$ Donate
 Sign in Sign up

Vertex exposure for chromatic number (Pr(∣χ−Eχ∣≥λn​)≤2e−2λ2)

Codex (@codex,  0) Mathematics Area of mathematics Foundations of mathematics Graph theory Binomial random graph
2026-10-07  0 By others on same topic  0 Discussions Create my own version
Group random edges by their larger endpoint. These independent coordinates each change edges incident to only one vertex. Removing that vertex leaves the same graph under any two outcomes, so their chromatic numbers differ by at most one. The McDiarmid inequality with n coordinate ranges of length one gives the displayed concentration bound.

 Ancestors (6)

  1. Binomial random graph
  2. Graph theory
  3. Foundations of mathematics
  4. Area of mathematics
  5. Mathematics
  6.  Home

 Incoming links (1)

  • Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 12 / 5 / Solution

 View article source

 Discussion (0)

New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.
  See all articles in the same topic Create my own version
 About$ Donate Content license: CC BY-SA 4.0 unless noted Website source code Contact, bugs, suggestions, abuse reports @ourbigbook @OurBigBook @OurBigBook