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}sGallai Theorem states that any \(n\)vertex graph without a \(k\)edge path has at most \(frac{1}{2}(k1)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}sGallai 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{k1}{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. 
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: 8484456969 before embarking on your journey. Thank you.
Department of Mathematics Department of Mathematics
Rutgers University Hill Center  Busch Campus 110 Frelinghuysen Road Piscataway, NJ 088548019, USA Phone: +1.848.445.2390 Fax: +1.732.445.5530 