Turán numbers, norm graphs, quasirandomness

Abstract: 

The Turán number of a (hyper)graph $H$, defined as the maximum number of (hyper)edges in an $H$-free (hyper)graph on a given number of vertices, is a fundamental concept of extremal combinatorics. The behaviour of the Turán number is well-understood for non-bipartite graphs, but for bipartite $H$ there are more questions than answers. A particularly intriguing half-open case is the one of complete bipartite graphs.

The projective norm graphs $NG(q,t)$ are algebraically defined graphs which provide tight constructions in the Turán problem for complete bipartite graphs $H=K_{t,s}$ when $s>(t–1)!.$ The $K_{t,s}$-freeness of $NG(q,t)$ is a very much atypical property: in a random graph with the same edge density a positive fraction of $t$-tuples are involved in a copy of $K_{t,s}.$ Yet, projective norm graphs are random-like in various other senses. Most notably their second eigenvalue is of the order of the square root of the degree, which, through the Expander Mixing Lemma, implies further quasirandom properties concerning the density of small enough subgraphs. In this talk we explore how far this quasirandomness goes. The main contribution of our proof is the estimation, and sometimes determination, of the number of solutions of certain norm equation system over finite fields.

Joint work with Tomas Bayer, Tamás Mészáros, and Lajos Rónyai.

This is a seminar of the Combinatorial Mathematics Society of Australasia.

To attend: email cmsa-webinar@monash.edu with the subject 'subscribe' to receive zoom details. [You only need to subscribe once, not for future talks.]