| 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$. 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