Some sharp lower bounds for the bipartite Turán number of theta graphs

Abstract

We expand Conlon's random algebraic construction to show that for any odd number $k\ge 3$ exists a natural number $c_k$ (the same as Conlon's) such that $\mathrm{ex}(n^a,n,{\theta }_{k,c_k})={\Omega }_{k,a}((n^{1+a}{)}^{\frac{k+1}{2k}})$, with $a\in [\frac{k-1}{k+1},1)$. Where given a graph $H$, we denote by $\mathrm{ex}(n,m,H)$ the maximum number of edges an $H-$free bipartite graph can have when the cardinalities of its parts are $n$ and $m$. Also, we denote with ${\theta }_{k,l}$ the graph where two vertices are connected through $l$ disjoint paths of length $k$.

arXiv commentarXiv admin note: text overlap with arXiv:1411.0856 by other authors