Home > Academic Announcements > (Aug. 13) Forbidding tight cycles in hypergraph

(Aug. 13) Forbidding tight cycles in hypergraph

Last updated :2018-08-02

Topic: Forbidding tight cycles in hypergraphs
Speaker: Assistant Professor Hao Huang
(Emory University)
Time: 9:00-10:00 am, Monday, August 13, 2018
Venue: Room 416, Mathematics Building, Guangzhou South Campus, SYSU

Abstract:
A tight $k$-uniform $/ell$-cycle, denoted by $TC_/ell^k$, is a $k$-uniform hypergraph whose vertex set is $v_0, /cdots, 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, S/'os and, independently, Verstra/"ete 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.