Graphs and Matroids Seminar - Logan GroutExport this event to calendar

Thursday, October 10, 2019 — 4:00 PM EDT

Title: A Pseudoforest Analogue of the Strong Nine Dragon Tree Conjecture

Speaker: Logan Grout
Affiliation: University of Waterloo
Room: MC 5501

Abstract:

In 2016, Jiang and Yang proved the Nine Dragon Tree Conjecture, a strengthening of the classical arboricity result of Nash-Williams (1964). On the way to developing this proof, Fan, Lim Song, and Yang proved an analogous result for decomposing graphs into pseudoforests, which is a strengthening of Hakimi’s Theorem.

We attempt to follow the same path and prove a pseudo forest analogue of the Strong Nine Dragon Tree Conjecture: that, for any positive integers k and d, if  G is a graph with maximum average degree at most 2k+2d/(k+d+1), then G decomposes into k+1 pseudoforests, with one of these pseudoforests containing components with at most d edges.

Location 
MC - Mathematics & Computer Building
5501
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
  1. 2019 (143)
    1. October (14)
    2. September (15)
    3. August (9)
    4. July (17)
    5. June (18)
    6. May (16)
    7. April (9)
    8. March (24)
    9. February (13)
    10. January (8)
  2. 2018 (138)
    1. December (2)
    2. November (18)
    3. October (14)
    4. September (9)
    5. August (2)
    6. July (10)
    7. June (13)
    8. May (17)
    9. April (9)
    10. March (19)
    11. February (14)
    12. January (11)
  3. 2017 (103)
  4. 2016 (137)
  5. 2015 (136)
  6. 2014 (88)
  7. 2013 (48)
  8. 2012 (39)
  9. 2011 (36)
  10. 2010 (40)
  11. 2009 (40)
  12. 2008 (39)
  13. 2007 (15)