Uniform edge distribution in hypergraphs is hereditary

Dhruv Mubayi ; Vojtĕch Rödl

The electronic journal of combinatorics, Tome 11 (2004) no. 1

Résumé

Let $\alpha \in (0,1), l \ge 2$ and let ${\cal H}_n$ be an $l$-graph on $n$ vertices. ${\cal H}_n$ is $(\alpha, \xi)$-uniform if every $\xi n$ vertices of ${\cal H}_n$ span $(\alpha \pm\xi) {\xi n\choose l}$ edges. Our main result is the following. For all $\widetilde{\delta}$, there exist $\delta, r, n_0$ such that, if $n>n_0$ and ${\cal H}_n^{(l)}$ is $(\alpha, \delta)$-uniform, then all but $\exp\{-r^{1/l}/20\}{n\choose r}$ $r$-sets of vertices induce a subhypergraph that is $(\alpha,\widetilde{\delta})$-uniform. We also present the following application. Let ${\cal F}$ be a fixed $l$-graph, and $c>0$. Then there is an $n_0$ and $r'$ such that: If ${\cal H}$ is an $n$ vertex $l$-graph ($n>n_0$) such that the deletion of any $c n^l$ edges of ${\cal H}$ leaves an $l$-graph that admits no homomorphism into ${\cal F}$, then there exists ${\cal H}' \subset {\cal H}$ on $r'$ vertices, that also admits no homomorphism into ${\cal F}$. This extends a recent result of Alon and Shapira, who proved it when ${\cal F}$ is a complete graph.

Détail

DOI : 10.37236/1808

Classification : 05C35, 05C15, 05C65, 05D05
Mots-clés : Ramsey Turán problems, extremal hypergraph theory