Exploring Projective Norm Graphs

arXiv1908.05190MaRDI QIDQ6323656FDOQ6323656

Tibor Szabó, Tamás Mészáros, Lajos Rónyai, Tomáš Bayer

Publication date: 14 August 2019

Abstract: The projective norm graphs $extNG(q,t)$ provide tight constructions for the Tur'an number of complete bipartite graphs $K_{t,s}$ with $s>(t-1)!$. In this paper we determine their automorphism group and explore their small subgraphs. To this end we give quite precise estimates on the number of solutions of certain equation systems involving norms over finite fields. The determination of the largest integer $s_t$, such that the projective norm graph $extNG(q,t)$ contains $K_{t,s_t}$ for all large enough prime powers $q$ is an important open question with far-reaching general consequences. The best known bounds, $t-1leq{s}_{t}leq(t-1)!$, are far apart for $tgeq4$. Here we prove that $extNG(q,4)$ does contain (many) $K_{4,6}$ for any prime power $q$ not divisble by $2$ or $3$. This greatly extends recent work of Grosu, using a completely different approach. Along the way we also count the copies of any fixed $3$-degenerate subgraph, and find that projective norm graphs are quasirandom with respect to this parameter. Some of these results also extend the work of Alon and Shikhelman on generalized Tur'an numbers. Finally we also give a new, more elementary proof for the $K_{4,7}$-freeness of $extNG(q,4)$.

This page was built for publication: Exploring Projective Norm Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6323656)