Title: Extremal Cuts and Isoperimetry in Random Cubic Graphs
Speaker: Prof. Gregory B. Sorkin
Affiliation: Dept of Mathematics, The London School of Economics and Political Science (LSE)
Location: LT139 Huxley Building
Time: 14:00 – 15:00

Abstract. 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 known that a random cubic graph has a minimum bisection of size at most 1/6 times its order (indeed this is known for all cubic graphs), and we reduce this upper bound to below 1/7 (to 0.13993) by analyzing an algorithm with a couple of surprising features. We increase the corresponding lower bound on minimum bisection using the Hamilton cycle model of a random cubic graph. We use the same Hamilton cycle approach to decrease the upper bound on maximum cut. We will discuss some related conjectures.