Local algorithms, regular graphs of large girth, and random regular graphs

Understand

We introduce a general class of algorithms and supply a number of general results useful for analysing these algorithms when applied to regular graphs of large girth.

• As a result, we can transfer a number of results proved for random regular graphs into (deterministic) results about all regular graphs with sufficiently large girth.
• This is an uncommon direction of transfer of results, which is usually from the deterministic setting to the random one.
• In particular, this approach enables, for the first time, the achievement of results equivalent to those obtained on random regular graphs by a powerful class of algorithms which contain prioritised actions.