Manuscript · February 2014

We study the problem of finding *large cuts in $d$-regular triangle-free graphs*. In prior work, Shearer (1992) gives a randomised algorithm that finds a cut of expected size $(1/2 + 0.177/\sqrt{d})m$, where $m$ is the number of edges. We give a simpler algorithm that does much better: it finds a cut of expected size $(1/2 + 0.28125/\sqrt{d})m$. As a corollary, this shows that in any $d$-regular triangle-free graph there exists a cut of at least this size.

Our algorithm can be interpreted as a very efficient *randomised distributed algorithm*: each node needs to produce only one random bit, and the algorithm runs in one synchronous communication round. This work is also a case study of applying *computational techniques* in the design of distributed algorithms: our algorithm was designed by a computer program that searched for optimal algorithms for small values of $d$.