Uniform edge distribution in hypergraphs is hereditary (Q1883672): Difference between revisions
From MaRDI portal
Created a new Item |
Set profile property. |
||
(3 intermediate revisions by 2 users not shown) | |||
Property / author | |||
Property / author: Vojtěch Rödl / rank | |||
Property / author | |||
Property / author: Vojtěch Rödl / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 06:02, 5 March 2024
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
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