Seminars & Colloquia Calendar
"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}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. 
R. Shapiro Organizer's Page
Chiara Damiolini, Ian Coley and Franco Rota Charles Weibel Organizer's Page
Brooke Logan
Wujun Zhang Organizer's webpage
P. Gupta, X.Huang and J. Song Organizer's webpage
Swastik Kopparty, Sepehr Assadi Seminar webpage
Jeffry Kahn, Bhargav Narayanan, Jinyoung Park Organizer's webpage
Brooke Ogrodnik, Website
Robert DoughertyBliss and Doron Zeilberger > homepage
Paul Feehan, Daniel Ketover, Natasa Sesum Organizer's webpage
Lev Borisov, Emanuel Diaconescu, Angela Gibney, Nicolas Tarasca, and Chris Woodward Organizer's webpage
Jason Saied Seminar webpage
Brian Pinsky, Rashmika Goswami website
Quentin Dubroff Organizer's webpage
James Holland; Organizer website
Edna Jones Organizer's webpage
Brooke Ogrodnik website
Yanyan Li, ZhengChao Han, Jian Song, Natasa Sesum Organizer's Webpage
Organizer: Luochen Zhao
Yanyan Li, ZhengChao Han, Natasa Sesum, Jian Song Organizer's Page
Lisa Carbone, YiZhi Huang, James Lepowsky, Siddhartha Sahi Organizer's webpage
Simon Thomas website
Kasper Larsen, Daniel Ocone and Kim Weston Organizer's page
Joel Lebowitz, Michael Kiessling
Yanyan Li, Haim Brezis Organizer's Webpage
Stephen D. Miller, John C. Miller, Alex V. Kontorovich, Alex Walker seminar website
Stephen D. Miller
Brooke Ogrodnik, Website
Organizers: Yanyan Li, Z.C. Han, Jian Song, Natasa Sesum
Yael Davidov Seminar webpage
Kristen Hendricks, Xiaochun Rong, Hongbin Sun, Chenxi Wu Organizer's page
Fioralba Cakoni Seminar webpage
Ebru Toprak, Organizer
Organizer's webpage: Organizer's webpage
 Show events from all categories
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: 8484456969 before embarking on your journey. Thank you.