# Large Cuts with Local Algorithms on Triangle-Free Graphs

Keywords:
Graph theory, Regular graphs, Cuts

### Abstract

Let $G$ be a $d$-regular triangle-free graph with $m$ edges. We present an algorithm which finds a cut in $G$ with at least $(1/2 + 0.28125/\sqrt{d})m$ edges in expectation, improving upon Shearer's classic result. In particular, this implies that any $d$-regular triangle-free graph has a cut of at least this size, and thus, we obtain a new lower bound for the maximum number of edges in a bipartite subgraph of $G$.Our algorithm is simpler than Shearer's classic algorithm and it can be interpreted as a very efficient

*randomised distributed (local) algorithm*: each node needs to produce only one random bit, and the algorithm runs in one round. The randomised algorithm itself was discovered using

*computational techniques*. We show that for any fixed $d$, there exists a weighted neighbourhood graph $\mathcal{N}_d$ such that there is a one-to-one correspondence between heavy cuts of $\mathcal{N}_d$ and randomised local algorithms that find large cuts in any $d$-regular input graph. This turns out to be a useful tool for analysing the existence of cuts in $d$-regular graphs: we can compute the optimal cut of $\mathcal{N}_d$ to attain a lower bound on the maximum cut size of any $d$-regular triangle-free graph.