Title: Extremal Problems for Paths in Graphs and Hypergraphs
Speaker: Jacques Verstraete, UC San Diego
Date: Monday, April 24, 2017 2:00 pm
Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ
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.
See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math