BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: 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 verti
ces\, is a fundamental concept of extremal graph theory. The behaviour of t
he Turán number is well-understood for non-bipartite graphs\, but for bipar
tite H there are more questions than answers. A particularly intriguing hal
f-open case is the one of complete bipartite graphs. The projective norm gr
aphs $NG(q\,t)$ are algebraically defined graphs which provide tight constr
uctions in the Tur\'an problem for complete bipartite graphs $H=K_{t\,s}$ w
hen $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\, projecti
ve 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 propertie
s concerning the density of small enough subgraphs. In this talk we explore
how far this quasirandomness goes. The main contribution of our proof is t
he estimation\, and sometimes determination\, of the number of solutions of
certain norm equation system over finite fields. Joint work with Tomas Bay
er\, Tam\'as M\'esz\'aros\, and Lajos R\'onyai.
DTSTAMP:20191108T131200
DTSTART:20191111T141500
CLASS:PUBLIC
LOCATION:Freie Universität Berlin \n Institut für Informatik \n Takustr. 9
\n 14195 Berlin \n Room 005 (Ground Floor)
SEQUENCE:0
SUMMARY:Tibor Szabó (Freie Universität Berlin): Turán numbers\, projective
norm graphs\, quasirandomness
UID:95692516@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20191111-L-Szabo.html
END:VEVENT
END:VCALENDAR