Concept

Monotone property

A property of graphs that cannot be destroyed by adding edges, such as being connected or containing a triangle. Every such property has a threshold in random graphs, and whether the threshold is sharp is decided by locality.

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

One threshold narrowing, one staying wide. Probability curves for connectivity and for containing a triangle, plotted against the edge probability as a multiple of each property's own threshold, at several graph sizes.

Sharp, or merely a threshold

Every monotone property of a random graph has a threshold. Some of them turn on over a range that shrinks relative to the threshold as the graph grows, and some do not — and which kind a property is turns out to be decided by whether it is about a local structure or about the whole graph.

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.

Phase transition Threshold Backtracking Conjecture First moment Locality Measurement Random graph Satisfiability Second moment

All concepts