Presentation Name: 午间学术星空(中国)会(九十四):Graph partitions with degree constraint
Presenter: 吴河辉
Date: 2018-03-30
Location: 光华东主楼1501
Abstract:

A classical result showed by Stiebitz in 1996 stated that a graph with minimum degree $s+t+1$ contains a vertex partition $(A, B)$,  such that $G[A]$ has minimum degree at least $s$ and $G[B]$ has minimum degree at least $t$.

Motivated by this result, it was conjectured that for any non- negative real number $s$ and $t$, such that if $G$ is a non-null graph with average degree at least $s + t + 2$, then there exist a vertex partition $(A, B)$ such that $G[A]$ has average degree at least $s$ and $G[B]$ has average degree at least $t$.  

 
Recently, with Dr. Yan Wang at Facebook, we fully proved the conjecture. 
 
In this talk, we will show how to consider it as an integer programing problem, and apply some basic linear algebra technique to solve the problem. In the same talk, we will also show how we use probabilistic method to solve analogue problems.
 
Annual Speech Directory: No.71

220 Handan Rd., Yangpu District, Shanghai ( 200433 )| Operator:+86 21 65642222

Copyright © 2016 FUDAN University. All Rights Reserved