New constructions of unbalanced $\{C_4,{\theta }_{3,t}\}$-free bipartite graphs

Abstract

In 1979, Erdős conjectured that if $m=O(n^{2/3})$, then $ex(n,m,\{C_4,C_6\})=O(n)$. This conjecture was disproven by several papers and the current best-known bounds for this problem are $$c_1{n}^{1+\frac{1}{15}}\le ex(n,n^{2/3},\{C_4,C_6\})\le c_2{n}^{1+1/9}$$ for some constants $c_1,c_2$. A consequence of our work here proves that $$ex(n,n^{2/3},\{C_4,{\theta }_{3,4}\})=\Theta (n^{1+1/9}).$$ More generally, for each integer $t\ge 2$, we establish that $$ex(n,n^{\frac{t+2}{2t+1}},\{C_4,{\theta }_{3,t}\})=\Theta (n^{1+\frac{1}{2t+1}})$$ by demonstrating that subsets of points $S\subseteq \text{PG}(n,q)$ for which no $t+1$ points lie on a line give rise to $\{C_4,{\theta }_{3,t}\}$-free graphs, where PG$(n,q)$ is the projective space of dimension $n$ over the finite field of $q$ elements.