Uniform edge distribution in hypergraphs is hereditary (Q1883672): Difference between revisions

Summary: Let \(\alpha\in(0,1)\), \(l\geq 2\) and let \({\mathcal H}_n\) be an \(l\)-graph on \(n\) vertices. \({\mathcal H}_n\) is \((\alpha,\xi)\)-uniform if every \(\xi n\) vertices of \({\mathcal 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 \({\mathcal 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 \({\mathcal F}\) be a fixed \(l\)-graph, and \(c>0\). Then there is an \(n_0\) and \(r'\) such that: If \({\mathcal H}\) is an \(n\) vertex \(l\)-graph \((n>n_0\)) such that the deletion of any \(cn^l\) edges of \({\mathcal H}\) leaves an \(l\)-graph that admits no homomorphism into \({\mathcal F}\), then there exists \({\mathcal H}'\subset {\mathcal H}\) on \(r'\) vertices, that also admits no homomorphism into \({\mathcal F}\). This extends a recent result of Alon and Shapira, who proved it when \({\mathcal F}\) is a complete graph.