FoCM 2014 conference
Workshop A4 - Graph Theory and Combinatorics
No date set
Counting $k$-uniform linear hypergraphs in sparse pseudorandom hypergraphs
Guilherme Oliveira Mota
USP - University of São Paulo, Brazil - mota@ime.usp.br
We give a counting lemma for the number of copies of linear $k$-uniform connector-free hypergraphs (connector is a generalization of triangle for hypergraphs) that are contained in some sparse hypergraphs $G$. Let $H$ be a linear $k$-uniform connector-free hypergraph and let $G$ be a $k$-uniform hypergraph with $n$ vertices. Set $d_H=\max\{\delta(J)\colon J\subset H\}$ and $D_H=\min\{kd_H,\Delta(H)\}$. We proved that if the vertices of $G$ do not have large degree, small families of $(k-1)$-element sets of $V(G)$ do not have large common neighbourhood and most of the pairs of sets in ${V(G)\choose k-1}$ have the 'right' number of common neighbours, then the number of embeddings of $H$ in $G$ is $(1+o(1))n^{|V(H)|}p^{|E(H)|}$, given that $p\gg n^{-1/D_H}$ and $|E(G)|={n\choose k}p$. This generalizes a result by Kohayakawa, R\"odl and Sissokho [Embedding graphs with bounded degree in sparse pseudo-random graphs, Israel J. Math. 139 (2004), 93-137], who proved that, for $p$ as above, this result holds for graphs, where $H$ is a triangle-free graph.
Joint work with Yoshiharu Kohayakawa, Mathias Schacht and Anusch Taraz.