Mathematics Department - Discrete Math - Fall 2014

Discrete Math - Fall 2014


Jeffry Kahn, Hao Huang


Past Talks

Wednesday, November 19th

Special Discrete Math

Justin Gilmer , Rutgers University

"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, University of Michigan

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

This page was last updated on August 29, 2014 at 01:59 pm and is maintained by
For questions regarding courses and/or special permission, please contact
For questions or comments about this site, please contact
© 2014 Rutgers, The State University of New Jersey. All rights reserved.