University of Birmingham > Talks@bham > Combinatorics and Probability Seminar > Extremal Cuts and Isoperimetry in Random Cubic Graphs

## Extremal Cuts and Isoperimetry in Random Cubic GraphsAdd to your list(s) Download to your calendar using vCal - Gregory Sorkin (London School of Economics)
- Tuesday 07 November 2017, 15:00-16:00
- Watson LTA.
If you have a question about this talk, please contact Guillem Perarnau. Random 3-regular graphs are a particularly simple random structure, the 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 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 (from 1/9.9 to 0.10133) 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 (from 1.4026 to 1.40031). We will discuss some related conjectures. This talk is part of the Combinatorics and Probability Seminar series. ## This talk is included in these lists:Note that ex-directory lists are not shown. |
## Other listsGeometry and Mathematical Physics seminar analysis Physics and Astronomy Colloquia## Other talksHydrodynamics and Chaos in Quantum Matter Attacking and Defending Cloud Networks Multi-dimensional vector assignment problems (MVA) : Complexity, Approximation and Algorithms How hard is LWE anyway? FENL: an ISE to mitigate analogue micro-architectural leakage Verification of Byzantine Fault Tolerant Systems |