Forbidding tight cycles in hypergraphs

Series: 
Combinatorics Seminar
Friday, February 16, 2018 - 3:00pm
1 hour (actually 50 minutes)
Location: 
Skiles 005
,  
Emory University
,  
Organizer: 
A tight k-uniform \ell-cycle, denoted by TC_\ell^k, is a k-uniform hypergraph whose vertex set is v_0, ..., v_{\ell-1}, and the edges are all the k-tuples {v_i, v_{i+1}, \cdots, v_{i+k-1}}, with subscripts modulo \ell. Motivated by a classic result in graph theory that every n-vertex cycle-free graph has at most n-1 edges, Sos and, independently, Verstraete asked whether for every integer k, a k-uniform n-vertex hypergraph without any tight k-uniform cycles has at most \binom{n-1}{k-1} edges. In this talk I will present a construction giving negative answer to this question, and discuss some related problems. Joint work with Jie Ma.