Carsten Thomassen in 1989 conjectured that if a graph has minimum degree more than the number of atoms in the universe ($\delta(G)\ge 10^{10^{10}}$), then it contains a pillar, which is a graph that consists of two vertex-disjoint cycles of the same length, $s$ say, along with $s$ vertex-disjoint paths of the same length which connect matching vertices in order around the cycles. Despite the simplicity of the structure of pillars and various developments of powerful embedding methods for paths and cycles in the past three decades, this innocent looking conjecture has seen no progress to date. In this talk, we will try to give an idea of the tools used in the proof of this conjecture, which consists of building a pillar (algorithmically) in sublinear expanders. This is joint work with Hong Liu.
기초과학연구원 이산수학그룹