Graf färgning är utan tvekan det mest uttömmande studerade problemet inom området ungefärlig räkning. Det förmodas att det finns en helt polynom-tid (randomized) approximation system (FP-TAS/FPRAS) för att räkna antalet korrekta färgningar så länge q ≥  på + 1, där q är antalet färger och  till är den maximala graden av grafen. Gränsen för q =  på + 1 är den unika tröskeln för Gibbs åtgärd på vanliga oändliga träd. Men gissningen förblev öppen även för alla fasta  till ≥ 3 (De fall av  till = 1, 2 är triviala). I detta papper, Vi utformar en FPTAS för att räkna antalet riktiga 4-färger på grafer med maximal grad 3 och därmed bekräfta gissningen i fallet  till = 3. Detta är första gången att uppnå denna optimala gräns av q =  på + 1. Tidigare kräver det bästa FPRAS q > 11 6 och det bästa deterministiska FPTAS kräver q > 2,5819 + 1 för allmänna grafer. När det gäller  på = 3, det bästa tidigare resultatet är en Fpras för att räkna korrekt 5-färger. Vi noterar att det finns en barriär att gå bortom q =  på + 2 för en enda plats Glauber dynamik baserad FPRAS och vi övervinna detta genom korrelation förfall strategi. Dessutom utvecklar vi ett antal nya tekniker för korrelation sönderfall metod som kan hitta tillämpningar i andra ungefärliga räkna problem.
För specialfallet Δ = 3, Lu et al. REF ger en korrelation sönderfallsalgoritm för att räkna 4-färger.
An FPTAS for Counting Proper Four-Colorings on Cubic Graphs
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}