## University COVID-19 update

### Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

# Tutte seminar - Jacques Verstraete

Friday, August 1, 2008 — 3:30 PM to 4:30 PM EDT

## On the structure of binary matroids

Speaker: Jacques Verstraete University of California, San Diego Mathematics & Computer Building (MC) 5158

### Abstract:

An old conjecture Erdős states that every graph of minimum degree three has a cycle of length a power of two. While this might appear more a puzzle than a serious problem, the real question is to determined properties of the structure of the set of cycle lengths in a graph of prescribed minimum degree. We give the first almost constant bound on the minimum degree of a graph with no cycle of length in an infinite increasing sequence of even numbers growing no faster than the tower sequence:

22, 222, 2222, 22222, …

Surprisingly, this result is almost best possible, in that there is an $n$-vertex graph of average degree about log n with no cycle of length in the sequence:

23, 234, 2345, 23456, …

We end with some conjectures which suggested analogous results for odd cycles.

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

Waterloo, ON N2L 3G1

### November 2020

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