MATH Seminar

Title: Weakly quasirandom hypergraphs
Seminar: SIAM Student Chapter
Speaker: Mathias Schacht of Emory University
Contact: Vojtech Rodl, rodl@mathcs.emory.edu
Date: 2010-03-15 at 4:00PM
Venue: MSC W303
Download Flyer
Abstract: We consider quasi-random properties of $k$-uniform hypergraphs. The central notion is uniform edge distribution with respect to large vertex sets. We find several equivalent characterisations of this property and this work can be viewed as a natural extension of the well known Chung-Graham-Wilson theorem for quasi-random graphs.\\ \\ Those charecterisation for hypergraphs have an interesting consequence for the theory of quasi-random graphs. Let $K_k$ be the complete graph on $k$ vertices and let $M(k)$ be the line graph of the graph of the $k$-dimensional hypercube. We show that the pair of graphs $(K_k,M(k))$ has the following property: if the number of copies of both $K_k$ and $M(k)$ in another (large) graph $G$ are as expected in the random graph of density $d$, then $G$ is quasi-random (in the sense of the Chung-Graham-Wilson theorem) with density close to $d$. Those pairs of non-bipartite graphs with this property.