Department of

Mathematics


Seminar Calendar
for events the day of Tuesday, June 23, 2020.

     .
events for the
events containing  

(Requires a password.)
More information on this calendar program is available.
Questions regarding events or the calendar should be directed to Tori Corkery.
       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

2:00 pm in Zoom,Tuesday, June 23, 2020

Linear cycles of consecutive lengths in linear hypergraphs

Tao Jiang (Miami University)

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.