the chromatic and independence numbers of a random graph
Two of the hardest combinatorial parameters of a graph are its independence number alpha(G) (the size of the largest set of vertices with no edges among them) and its chromatic number chi(G) (the fewest colours needed to colour the vertices so adjacent ones differ). Determining either is NP-hard for general graphs, yet for the random graph G(n,p) both are pinned down with stunning precision — a triumph of the probabilistic method and of concentration. The question they answer is: how 'spreadable' is a random graph (large independent set?) and how 'cohesive' (many colours needed?), and how sharply are these determined?
Take the dense case p = 1/2 for concreteness. The independence number is governed by the second-moment method on the count of independent sets of a given size: an independent set of size k exists with probability tending to 1 or 0 according as 2^k 2^(-C(k,2)) is large or small, which gives alpha(G) concentrated on essentially two consecutive integers near 2 log_2 n. The same calculation applied to cliques (complete subgraphs) shows the clique number is also about 2 log_2 n with two-point concentration — a famous result of Bollobas and Erdos and of Matula. The chromatic number is then forced from below by chi >= n/alpha (each colour class is an independent set of size at most alpha), giving chi(G) >= n/(2 log_2 n); the deep theorem of Bollobas (using martingale concentration, the Azuma/vertex-exposure inequality) shows this lower bound is tight: chi(G(n,1/2)) is asymptotically n/(2 log_2 n). For sparse G(n, c/n) the chromatic number is concentrated on a bounded number of values, and Shamir-Spencer plus Luczak showed it is whp one of at most two consecutive integers — even though we often cannot say WHICH two.
These results matter as the showcase of concentration of measure in combinatorics: the chromatic number, an enormously complex global functional, is concentrated in a window of width O(1) or O(sqrt(n)) by martingale arguments, even when its exact value is unknown. They also drive the theory of graph colouring algorithms and the analysis of constraint-satisfaction thresholds. The honesty to keep is sharp here: concentration does NOT mean we know the value. The vertex-exposure martingale (revealing the graph one vertex at a time) changes chi by at most 1 per step, so Azuma gives concentration within O(sqrt(n)) immediately and finer arguments give a window of two integers — but pinning down the exact constant or the exact pair of values was open for decades, and for sparse graphs the precise location of the k-colourability threshold is a deep and only recently resolved problem (via the second-moment method with weighting and ideas from statistical physics).
For G(n, 1/2) with n = 1024, the independence number is about 2 log_2 n = 20 (concentrated on about two values), and the chromatic number is about n/(2 log_2 n) = 1024/20 about 51. The lower bound chi >= n/alpha is essentially tight: you cannot do much better than n/alpha colours because each colour can absorb at most one independent set's worth of vertices.
alpha about 2 log_2 n drives chi about n/(2 log_2 n); concentration nails the window even when the exact value is hard.
Concentration is not the same as knowing the value: the vertex-exposure martingale + Azuma give a two-integer window for chi long before anyone could say WHICH integers. Locating the sparse k-colourability threshold exactly is genuinely hard.