Seminars & Colloquia Calendar

Download as iCal file

Discrete Math

"Extremal problems for paths in graphs and hypergraphs"

Jacques Verstraete, UC San Diego

Location:  HILL 705
Date & time: Monday, 24 April 2017 at 2:00PM - 3:00PM



Time: 2:00 PM
Location: Hill 705
Abstract: The ErdH{o}s--Gallai Theorem states that any \(n\)-vertex graph without a \(k\)-edge path has at most \(frac{1}{2}(k-1)n\) edges. In this talk, various generalizations of this theorem for graphs and hypergraphs will be discussed, using a number of novel combinatorial, geometric and probabilistic methods. A representative of our results is the following generalization of the ErdH{o}s--Gallai Theorem. A {em tight \(k\)-path} is the hypergraph comprising edges \({i,i + 1,dots,i + r - 1}\), where \(1 leq i leq k\). We give a short proof that if \(H\) is an \(r\)-uniform \(n\)-vertex hypergraph not containing a tight \(k\)-path, then [ |H| leq frac{k-1}{r}{n choose r - 1}.] As noted by Kalai, equality holds whenever certain Steiner systems exist. This result proves a conjecture of Kalai for tight paths. We conclude with a number of open problems. One particular open problem, posed by V. S'{o}s and the speaker at AIM, is whether the maximum number of edges in an \(r\)-uniform \(n\)-vertex hypergraph containing no {em tight cycle} is at most \({n - 1 choose r - 1}\). Joint work with Z. F"{u}redi, T. Jiang, A. Kostochka and D. Mubayi.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.