Speaker 1: Sria Louis
Title: Asymptotically Almost Every 2r-regular Graph has an Internal Partition
Abstract: An internal partition of a graph is a partitioning of the vertex set into two parts such that for every vertex, at least half of its neighbors are on its side. It is easy to notice that such a partition doesn't always exist (e.g. - cliques), though, both the existence and finding of such a partition - are open problems.
Stiebitz (1996), responding to a problem of Thomassen (1983), made a breakthrough in this area, but the question and some interesting generalizations are still open.
We focus on regular graphs, and prove that for every positive integer r, asymptotically almost every 2r-regular graph has an internal partition.