Concept

Extension property

The property that for any two finite disjoint sets of vertices there is a vertex joined to everything in the first and nothing in the second. It characterises the infinite random graph, and finite graphs can have it for small sets.

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

Also named here as rado graph — the same set of essays touches all of them, so they are one junction rather than several.

The first 16 vertices of Rado's graph, joined by binary digits. Adjacency table and circular drawing of the Rado graph on vertices 0 to 15, where i < j are adjacent when bit i of j is 1; 32 edges.

The graph that coin tosses always make

Take infinitely many vertices and toss a coin for every pair to decide whether they are joined. The result is random in every detail — and, with probability one, it is always the same graph. The same graph can be written down without any coins, by joining two numbers when one binary digit of the larger is a one.

logic · Models

Which Paley graphs answer every small request. size 2: first passes at 13; size 3: first passes at 29; size 4: first passes at 89; primes checked up to 113.

The squares that answer every request

Rado's graph has, for any finite sets U and V, a vertex joined to all of U and none of V. A finite graph can only answer the small requests, and the Paley graphs — residues modulo a prime, joined when their difference is a square — are the classic way to build one. Checking every request exactly finds the thresholds: 13 residues answer every request of two, 29 every request of three, 89 every request of four. The theorem that guarantees it asks for 64, 576 and 4,096. Coin-toss graphs of the same sizes almost never manage it.

logic · Models

Named alongside it

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

Rado graph Random graph Back and forth Categoricity Isomorphism Paley graph Quadratic residue Ramsey number Universality Zero-one law

All concepts