Department of

May 2020 June 2020 July 2020 Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa 1 2 1 2 3 4 5 6 1 2 3 4 3 4 5 6 7 8 9 7 8 9 10 11 12 13 5 6 7 8 9 10 11 10 11 12 13 14 15 16 14 15 16 17 18 19 20 12 13 14 15 16 17 18 17 18 19 20 21 22 23 21 22 23 24 25 26 27 19 20 21 22 23 24 25 24 25 26 27 28 29 30 28 29 30 26 27 28 29 30 31 31

Tuesday, June 23, 2020

**Abstract:** A well-known result of Verstraete states that for each integer $k\geq 2$ every graph $G$ with average degree at least $8k$ contains cycles of $k$ consecutive even lengths, the shortest of which is at most twice the radius of $G$. Besides being interesting on its own, Verstraete's result also immediately implies that the Turan number $\mathrm{ex}(n, C_{2k})$ of the even cycle of length $2k$ is at most $8kn^{1+1/k}$, hence retrieving the classic theorem of Erdos and of Bondy and Simonovits with improved coefficients.

In this talk, we establish two extensions of Verstraete's result for linear cycles in linear $r$-uniform hypergraphs, where $r\geq 3$. A hypergraph is linear if every two edges intersect in at most one vertex. An $r$-uniform linear cycle $C^r_m$ is an $r$-uniform hypergraph consisting a cyclic list of edges $e_1,\dots,e_m$ such that consecutive edges intersect in one vertex and otherwise they are disjoint.

We prove that for all fixed $r\geq 3$, $k\geq 3$, there exists a constant $c_1=c_1(r)$ such that every linear $r$-uniform hypergraph $G$ with average degree $d(G)\geq c_1k$ contains linear cycles of $k$ consecutive even lengths, the shortest of which is at most $2 \frac{ \log n}{\log (d(G)/k)}$. In particular, as an immediate corollary, we retrieve the current best known upper bound on the linear Turan number of $C^r_{2k}$ with improved coefficients.

Furthermore, we show that for any fixed integers $r,k\geq 3$, there exists a constant $c_2=c_2(r)$ such that every $n$-vertex linear $r$-uniform graph with average degree $d(G)\geq c_2 k$, contains linear cycles of $k$ consecutive lengths (even and odd together), the shortest of which has length at most $6\frac{\log n}{\log (d(G)/k)} +5$. Both the degree condition and the shortest length among the cycles guaranteed are tight up to a constant factor. As a corollary it follows that there exists a constant $c_3=c_3(r)$ such that every $r$-uniform linear hypergraph with average degree at least $c_3$ contains an even cycle and an odd cycle of lengths at most $O(\log n)$, which is interesting on its own.

This is joint work with Jie Ma and Liana Yepremyan.

Please email Sean at SEnglish (at) illinois (dot) edu for the Zoom ID.