Matpic
mathematics, in pictures
Concept

First moment

The expected number of copies of a structure, used to prove none exists. A count taking whole values and having a small mean is usually zero, which needs no independence at all and gives one direction of a threshold immediately.

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

One piece, and connected, are different thresholds. Two curves against the average degree for graphs of 400 points: the largest component's share, rising from an average degree of one, and the probability of connectivity, rising only near the logarithm of the point count.

Two thresholds, not one

A random graph acquires a piece holding most of its points at average degree one, and is still not connected. Connectivity waits until the average degree reaches the logarithm of the size, and what holds it up is the very last isolated point.

probability · Random graphs 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.

ThresholdExpectationPhase transitionRandom graphSecond momentBacktrackingConjectureConnectivityCounting two waysCoupon collectorIsolated vertexMonotone property

All concepts