Uniform edge distribution in hypergraphs is hereditary
type: Item
instance of: scholarly article
title: Uniform edge distribution in hypergraphs is hereditary
zbMATH Open document ID: 1056.05083
author: Dhruv Mubayi
author: Vojtěch Rödl
published in: The Electronic Journal of Combinatorics
publication date: 2004-10-13T00:00:00Z
full work available at URL: https://eudml.org/doc/124214
full work available at URL: v11i1r55.html
review text: 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.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05D05
zbMATH DE Number: 2107497
zbMATH Keywords: Ramsey Turán problems
zbMATH Keywords: extremal hypergraph theory
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 2107497