## Organizer(s) | Jeffry Kahn, Hao Huang | ## Archive |

## Past Talks

## Wednesday, November 19th |

Special Discrete Math |

## Justin Gilmer , |

## "How many graphs on n vertices have exactly k triangles?" |

Time: 2:00 PM |

Location: Core 431 |

Abstract: We will show a local limit theorem for distribution of the
number of triangles in the Erdos-Renyi random graph G(n,p) where p in
(0,1) is a fixed constant. Our proof is based on bounding the
characteristic function psi(t) of the number of triangles, and uses
several different conditioning arguments to handle different ranges of t.
Joint work with Swastik Kopparty. |

## Monday, October 27th |

Special Discrete Math |

## Seth Pettie, |

## "Sharp Bounds on Davenport-Schinzel Sequences of Every Order" |

Time: 3:30 PM |

Location: Hill 705 |

Abstract: A Davenport-Schinzel sequence with order s is a sequence over
an n-letter alphabet that avoids alternating subsequences of the form
a..b..a..b.. with length s+2. They were originally used to bound the
complexity of the lower envelope of degree-s polynomials or any class of
functions that cross at most s times. They have numerous
applications in discrete geometry and the analysis of algorithms.
Let DS_s(n) be the maximum length of such a sequence. In this talk I'll present a new method for obtaining sharp bounds on DS_s(n) for every order s. This work reveals the unexpected fact that when s is odd, DS_s behaves essentially like the preceding DS_{s-1}. The results refute both common sense and a conjecture of Alon, Kaplan, Nivasch, Sharir, and Smorodinsky [2008]. Prior to this work, sharp upper and lower bounds were only known for s up to 3 and even s>3. The full manuscript is available at arXiv:1204.1086. An extended abstract was presented at the 2013 Symposium on Computational Geometry. |