Tutte seminar - Jacques VerstraeteExport this event to calendar

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

On the structure of binary matroids

Speaker: Jacques Verstraete
Affiliation: University of California, San Diego
Room: 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
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)