Turánnical hypergraphs. Issue 1 (18th February 2012)

• Record Type: Journal Article
• Authors: Allen, Peter; Böttcher, Julia; Hladký, Jan; Piguet, Diana
• Is Part Of: Random structures & algorithms. Volume 42:Issue 1(2013)
• Page Start: 29
• Page End: 58
• Publication Date: 2012-02-18
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20399
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main" xml:lang="en"> <title>Abstract</title> <p>This paper is motivated by the question of how global and dense restriction sets in results from extremal combinatorics can be replaced by less global and sparser ones. The result we consider here as an example is Turán's theorem, which deals with graphs <italic>G</italic> = ([<italic>n</italic>], <italic>E</italic>) such that no member of the <italic>restriction set</italic><tex-math notation="LaTeX"><![CDATA[\documentclass{article} \usepackage{mathrsfs} \usepackage{amsmath} \pagestyle{empty} \begin{document} \begin{align*}\mathcal {R}\end{align*} \end{document}]]></tex-math><inline-graphic xlink:href="ark:/27927/pgg1fbcbvjx" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /> = <tex-math notation="LaTeX"><![CDATA[\documentclass{article} \usepackage{mathrsfs} \usepackage{amsmath} \pagestyle{empty} \begin{document} \begin{align*}\left( {\begin{array}{*{20}c} {[n]} \\ r \\ \end{array} } \right)\end{align*} \end{document}]]></tex-math><inline-graphic xlink:href="ark:/27927/pgg1fbcbvnk" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /> induces a copy of <italic>K</italic><sub><italic>r</italic></sub>.</p> <p>Firstly, we examine what happens when this restriction set is replaced by <tex-math notation="LaTeX"><![CDATA[\documentclass{article} \usepackage{mathrsfs} \usepackage{amsmath} \pagestyle{empty} \begin{document} \begin{align*}\mathcal {R}\end{align*} \end{document}]]></tex-math><inline-graphic xlink:href="ark:/27927/pgg1fbcbvqp" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /> = {<italic>X</italic>∈ <tex-math notation="LaTeX"><![CDATA[\documentclass{article} \usepackage{mathrsfs} \usepackage{amsmath} \pagestyle{empty} \begin{document} \begin{align*}\left( {\begin{array}{*{20}c} {[n]} \\ r \\ \end{array} } \right)\end{align*} \end{document}]]></tex-math><inline-graphic xlink:href="ark:/27927/pgg1fbcbvr7" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />: <italic>X</italic> ∩ [<italic>m</italic>]≠<italic>∅︁</italic>}. That is, we determine the maximal number of edges in an <italic>n</italic> ‐vertex such that no <italic>K</italic><sub><italic>r</italic></sub> hits a given vertex set.</p> <p>Secondly, we consider sparse random restriction sets. An <italic>r</italic> ‐uniform hypergraph <tex-math notation="LaTeX"><![CDATA[\documentclass{article} \usepackage{mathrsfs} \usepackage{amsmath} \pagestyle{empty} \begin{document} \begin{align*}\mathcal R\end{align*} \end{document}]]></tex-math><inline-graphic xlink:href="ark:/27927/pgg1fbcbvvw" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /> on vertex set [<italic>n</italic>] is called <italic>Turánnical</italic> (respectively ε ‐<italic>Turánnical</italic>), if for any graph <italic>G</italic> on [<italic>n</italic>] with more edges than the Turán number <italic>t</italic><sub><italic>r</italic></sub>(<italic>n</italic>) (respectively (1 + ε)<italic>t</italic><sub><italic>r</italic></sub>(<italic>n</italic>) ), no hyperedge of <tex-math notation="LaTeX"><![CDATA[\documentclass{article} \usepackage{mathrsfs} \usepackage{amsmath} \pagestyle{empty} \begin{document} \begin{align*}\mathcal {R}\end{align*} \end{document}]]></tex-math><inline-graphic xlink:href="ark:/27927/pgg1fbcbvwf" mimetype="image" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /> induces a copy of <italic>K</italic><sub><italic>r</italic></sub> in <italic>G</italic>. We determine the thresholds for random <italic>r</italic> ‐uniform hypergraphs to be Turánnical and to be ε ‐Turánnical.</p> <p>Thirdly, we transfer this result to sparse random graphs, using techniques recently developed by Schacht [Extremal results for random discrete structures] to prove the Kohayakawa‐Łuczak‐Rödl Conjecture on Turán's theorem in random graphs.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012</p> </abstract>