Graph colouring via entropy compression

点击翻译按钮获取中文摘要

Graphs and hypergraphs are mathematical structures that model networks. Colouring graphs and hypergraphs is a key problem in many fields including scheduling, computing derivatives, cryptography, and coding theory. This project will apply a revolutionary method called "entropy compression" to produce new mathematical tools and algorithms for colouring graphs and hypergraphs. These results will have significant ramifications for the above applications, and will also be of fundamental importance in graph theory itself.