Concept

Second moment

The average of the square of a random quantity, which with the mean gives its variance. Showing the second moment is close to the square of the mean proves a count is rarely zero, the step that locates thresholds.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

A triangle appears when the count says it should. The measured probability of containing a triangle against the edge chance, on graphs of 200 points, beside the expected number of triangles capped at one.

Finding a threshold with two moments

Every monotone property of a random graph has a threshold, and locating one is nearly always the same two calculations — count what the property needs, and check the count does not concentrate on rare cases. The triangle is where the method is cleanest.

probability · Random graphs

The chance a random formula can be satisfied. n=20: 3:1.000 3.25:0.988 3.5:0.988 3.75:0.938 4:0.863 4.25:0.762 4.5:0.563 4.75:0.400 5:0.200 5.25:0.275 5.5:0.100 5.75:0.050 6:0.013; n=40: 3:1.000 3.25:1.000 3.5:1.000 3.75:0.963 4:0.863 4.25:0.575 4.5:0.425 4.75:0.138 5:0.050 5.25:0.025 5.5:0.037 5.75:0.000 6:0.000; n=80: 3:1.000 3.25:1.000 3.5:1.000 3.75:1.000 4:0.912 4.25:0.613 4.5:0.275 4.75:0.075 5:0.050 5.25:0.000 5.5:0.000 5.75:0.000 6:0.000.

A threshold nobody can place

Random three-literal clauses on n variables: below about 4.27 clauses a variable a formula can almost always be satisfied, above it almost never. The change is proved to be sharp and nobody has proved where it is. Counting solutions overshoots to 5.19, counting pairs of them fails outright, and every algorithm with a proof stops well short.

probability · Random graphs

Named alongside it

The objects these essays reach for when they reach for this one.

First moment Threshold Backtracking Conjecture Counting two ways Expectation Monotone property Phase transition Probabilistic method Random graph Satisfiability Variance

All concepts