The minimum bisection width of random cubic graphs is of interest because it is one of the simplest questions imaginable in extremal combinatorics, and also because the minimum bisection of (general) cubic graphs plays a role in the construction of efficient exponential-time algorithms, and it seems likely that random cubic graphs are extremal. It is... Read more »