Springe direkt zu Inhalt

Lecture by Tibor Szabó (Freie Universität Berlin): Turán numbers, projective norm graphs, quasirandomness

Nov 11, 2019 | 02:15 PM

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 graph theory. 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\'an 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\'as M\'esz\'aros, and Lajos R\'onyai.

Time & Location

Nov 11, 2019 | 02:15 PM

Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
Room 005 (Ground Floor)

Freie Universität Berlin
Technische Universität Berlin
Humboldt-Universität zu Berlin
Deutsche Forschungsgemeinschaft (DFG)