Abstract:
The Turán number of a (hyper)graph H, defined as the maximum number of (hyper)edges in an Hfree (hyper)graph on a given number of vertices, is a fundamental concept of extremal combinatorics. The behaviour of the Turán number is wellunderstood for nonbipartite graphs, but for bipartite H there are more questions than answers. A particularly intriguing halfopen 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 ttuples are involved in a copy of K_{t,s}. Yet, projective norm graphs are randomlike 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.
