Uniform edge distribution in hypergraphs is hereditary (Q1883672)

From MaRDI portal
Revision as of 12:00, 1 February 2024 by Import240129110113 (talk | contribs) (Added link to MaRDI item.)
scientific article
Language Label Description Also known as
English
Uniform edge distribution in hypergraphs is hereditary
scientific article

    Statements

    Uniform edge distribution in hypergraphs is hereditary (English)
    0 references
    0 references
    0 references
    13 October 2004
    0 references
    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.
    0 references
    Ramsey Turán problems
    0 references
    extremal hypergraph theory
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references