Ordered Graph Limits and Their Applications
summary
The paper defines a new limit object called an orderon (a function on R^2→[0,1] mixing an order coordinate and a variability coordinate), introduces a cut-shift (Katz-Schiff) distance, and proves completeness and compactness of the orderon space. A sampling theorem gives finite graphs within ε (size exp(O(1/ε))) and a pixelization lemma yields a finite description approximating any orderon in L1 while preserving forbidden-subgraph zeros. Applications: a simpler proof of the ordered graph removal lemma and a characterization of extremal distance by ordered stochastic block models.
AI-written summary · about
chapters (16)
- 0:00Intro
- 0:28Graph limits
- 2:10Some limits of combinatorial objects
- 3:28Ordered graphs
- 4:36A brief introduction to graphons
- 7:59What do we want from a limit object?
- 9:24Graphon as limit object for ordered graph
- 12:26Odd clique graphs
- 12:58Cut-shift distance
- 15:49Orderons
- 18:30Main results: Completeness & compacte
- 19:30Main results: Sampling & density
- 20:33Pixelization
- 22:16Application 1: Ordered graph removal len
- 24:05Application 2: What is the furthest ordere graph from a hereditary property?
- 26:48Some future directions