Combinatorics Seminar
Lujia Wang
UIC
The number of triple systems without even cycles
Abstract: For $k \ge 3$, a loose $k$-cycle $C_k$ is a hypergraph with distinct edges $e_1, e_2, \ldots, e_k$
such that consecutive edges (modulo $k$) intersect in exactly one vertex and all other pairs of edges
are disjoint. Our main result is that for every $l \ge 2$, there exists $c>0$ such that the number of triple
systems (3-uniform hypergraphs) with vertex set $[n]$ containing no $C_{2l}$ is at most $2^{cn^2}$.
An easy construction shows that the exponent is sharp in order of magnitude.
This extends the work of Morris and Saxton, who proved the analogous result for graphs
which was a longstanding problem.
We will give a sketch of the proof, which is different than that used for most
recent results about enumerating discrete structures. It contains some novel ingredients such as
the use of some quantitative estimates for an asymmetric version of the bipartite canonical
Ramsey theorem and the Turan problem for cycles modulo k in graphs. We will also talk about
some result for hypergraphs with larger uniformity that we obtained using the same proof.
This is a joint work with Dhruv Mubayi.
Monday February 6, 2017 at 2:00 PM in SEO 612