Independent sets and cuts in large-girth regular graphs

Abstract

We present a local algorithm producing an independent set of expected size $0.44533n$ on large-girth 3-regular graphs and $0.40407n$ on large-girth 4-regular graphs. We also construct a cut (or bisection or bipartite subgraph) with $1.34105n$ edges on large-girth 3-regular graphs. These decrease the gaps between the best known upper and lower bounds from $0.0178$ to $0.01$, from $0.0242$ to $0.0123$ and from $0.0724$ to $0.0616$, respectively. We are using local algorithms, therefore, the method also provides upper bounds for the fractional coloring numbers of $1/0.44533\approx 2.24554$ and $1/0.40407\approx 2.4748$ and fractional edge coloring number $1.5/1.34105\approx 1.1185$. Our algorithms are applications of the technique introduced by Hoppen and Wormald.

Cited by in corpus (4)

• Entropy and expansion
• Cubic graphs with small independence ratio
• Correlation bound for distant parts of factor of IID processes
• The threshold for SDP-refutation of random regular NAE-3SAT