Local Graph Coloring
summary
Constructs finitary factor of iid (ffiid) proper colorings on Z^d and proves tight coding-radius rates: for d≥2 three-color ffiid colorings exist with power-law tails (coding radius has infinite second moment), while four or more colors admit ffiid constructions with tower function tails (probability radius>r decays like an iterated-exponential tower), and these bounds are essentially tight. Methods combine percolation and hierarchical partitions to build examples, a height-function variance argument and block-comparison lemma (distributed-computing/Ramsey-type) to prove lower bounds.
AI-written summary · about
chapters (9)
- 0:00Introduction
- 0:54Definitions and motivation
- 5:54Warm-up example: Z2
- 10:45Coloring results summary
- 14:38Three coloring on Z2
- 20:17Proof of power-law bounds
- 27:05Four colorings and reductions
- 32:52Lower bounds and implications
- 42:04Concluding questions
related talks
51mAn Improved Bound for Regular Partitions of Hypergraph of Bounded VC_2 Dimension
39mBroadcasting on Directed Acyclic Graphs
44mTutorial on List Decodable Coding Schemes and Interactive Communication in Networks (Part 2 of 2)
30mLocal Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descr
56mSatisfiability Algorithms II
31mAlgebraic Coding Problems From Quantum Fault-Tolerance
01h 37mGraphons and Graph Limits 3
44mAlgorithmic Pirogov-Sinai Theory