Forbidden subgraphs in the norm graph

Valentina Pepe
Sapienza University of Rome

Simeon Ball
Universitat Politecnica de Catalunya

PDF

Minisymposium: FINITE GEOMETRY

Content: Let $H$ be a fixed graph. The {\em Tur\'an number} of $H$, denoted $ex(n,H)$, is the maximum number of edges that a graph with $n$ vertices and not containing a copy of $H$ can have. When $H$ is bipartite, in many cases, even the question of determining the right order of magnitude for $ex(n,H)$ is not known. We have the following bounds: $$ c n^{2-1/t} \leq ex(n,K_{t,s}) \leq \frac{1}{2}(s-1)^{\frac{1}{t}}n^{2-\frac{1}{t}}+\frac{1}{2}(t-1)n $$ where the lower one is probabilistic. In [1], the authors construct the so called \textit{norm graph} $\Gamma (t)$, proving that the upper bound is asymptotically sharp for $K_{t,s}, s> (t-1)!$. We prove that $\Gamma (t)$ also contains no copy of $K_{t+1,s},s \geq (t-1)!-1$, improving the known lower bound for $t=4$ and showing that $\Gamma (t)$ is the best determinist construction for $(t-1)!-1 \leq s \leq t!$, $t\geq 4$. \vspace{5mm} \noindent{\bf References:} \begin{itemize} \item[{[1]}] N. Alon, L. R\'onyai and T. Szab\'o, Norm-Graphs: Variations and applications, {\it J. Combin. Theory Ser. B}, {\bf 76} (1999) 280--290. \item[{[2]}] S. Ball and V. Pepe, Asymptotic improvements to the lower bound of certain bipartite Tur\'an numbers, {\it Combin. Probab. Comput.}, {\bf 21} (2012) 323--329. \item[{[3]}] S. Ball and V. Pepe, New forbidden graphs in the norm graph, arXiv: http://arxiv.org/abs/1502.01502. \end{itemize}

Back to all abstracts