Embedding tetrahedra into quasirandom hypergraphs

详细信息    查看全文

• 作者：Christian Reiher^a ; ^{Christian.Reiher@uni-hamburg.de" class="auth_mail" title="E-mail the corresponding author} ; Vojtěch Rö ; dl^b ; ¹ ; ^{rodl@mathcs.emory.edu" class="auth_mail" title="E-mail the corresponding author} ; Mathias Schacht^a ; ² ; ^{schacht@math.uni-hamburg.de" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Quasirandom hypergraphs ; Extremal graph theory ; Turá ; n's problem ; Tetrahedron
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2016
• 出版时间：November 2016
• 年：2016
• 卷：121
• 期：Complete
• 页码：229-247
• 全文大小：413 K

文摘

We investigate extremal problems for quasirandom hypergraphs. We say that a 3-uniform hypergraph class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895616300430&_mathId=si1.gif&_user=111111111&_pii=S0095895616300430&_rdoc=1&_issn=00958956&md5=14fb25a2a339b509dd696f2966a3f944" title="Click to view the MathML source">H=(V,E)class="mathContainer hidden">class="mathCode">$H=(V,E)$ is class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895616300430&_mathId=si2.gif&_user=111111111&_pii=S0095895616300430&_rdoc=1&_issn=00958956&md5=7ce611c34deb4b1e550c86e647c8b9c9" title="Click to view the MathML source">(d,η,class="imgLazyJSB inlineImage" height="8" width="9" alt="Full-size image (<1 K)" title="Full-size image (<1 K)" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0095895616300430-fx001.gif">)class="mathContainer hidden">class="mathCode">$(d,\eta ,\text{<inline-figure baseline="0.0"><link locator="fx001" type="simple" href="pii:S0095-8956(16)30043-0/fx001"></inline-figure>})$-quasirandom   if for any subset class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895616300430&_mathId=si3.gif&_user=111111111&_pii=S0095895616300430&_rdoc=1&_issn=00958956&md5=cc6e9875907484b46700933ba09cffe3" title="Click to view the MathML source">X⊆Vclass="mathContainer hidden">class="mathCode">$X\subseteq V$ and every set of pairs class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895616300430&_mathId=si4.gif&_user=111111111&_pii=S0095895616300430&_rdoc=1&_issn=00958956&md5=5c6a41524f75f42dc49a5be49a7b1170" title="Click to view the MathML source">P⊆V×Vclass="mathContainer hidden">class="mathCode">$P\subseteq V\times V$ the number of pairs class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895616300430&_mathId=si5.gif&_user=111111111&_pii=S0095895616300430&_rdoc=1&_issn=00958956&md5=6367d95838e9adcffdac361a6d8beb73" title="Click to view the MathML source">(x,(y,z))∈X×Pclass="mathContainer hidden">class="mathCode">$(x,(y,z))\in X\times P$ with class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895616300430&_mathId=si6.gif&_user=111111111&_pii=S0095895616300430&_rdoc=1&_issn=00958956&md5=43970257935c68e7fe62eaefa6e45240" title="Click to view the MathML source">{x,y,z}class="mathContainer hidden">class="mathCode">$\{x,y,z\}$ being a hyperedge of H   is in the interval class="mathmlsrc">class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895616300430&_mathId=si7.gif&_user=111111111&_pii=S0095895616300430&_rdoc=1&_issn=00958956&md5=829858343a61b7fa940092d17ed6d938">class="imgLazyJSB inlineImage" height="18" width="110" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0095895616300430-si7.gif">class="mathContainer hidden">class="mathCode">$d|X||P|\pm \eta |V{|}^3$. We show that for any class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895616300430&_mathId=si8.gif&_user=111111111&_pii=S0095895616300430&_rdoc=1&_issn=00958956&md5=4166c7dcca41ac741b6b7d1cb5172168" title="Click to view the MathML source">ε>0class="mathContainer hidden">class="mathCode">$\epsilon >0$ there exists class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895616300430&_mathId=si9.gif&_user=111111111&_pii=S0095895616300430&_rdoc=1&_issn=00958956&md5=a08b0d2f949aa5d21e531af93b8dc1af" title="Click to view the MathML source">η>0class="mathContainer hidden">class="mathCode">$\eta >0$ such that every sufficiently large class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895616300430&_mathId=si10.gif&_user=111111111&_pii=S0095895616300430&_rdoc=1&_issn=00958956&md5=63dfa06d4caf4036983d1d115b18ec44" title="Click to view the MathML source">(1/2+ε,η,class="imgLazyJSB inlineImage" height="8" width="9" alt="Full-size image (<1 K)" title="Full-size image (<1 K)" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0095895616300430-fx001.gif">)class="mathContainer hidden">class="mathCode">$(1/2+\epsilon ,\eta ,\text{<inline-figure baseline="0.0"><link locator="fx001" type="simple" href="pii:S0095-8956(16)30043-0/fx001"></inline-figure>})$-quasirandom hypergraph contains a tetrahedron, i.e., four vertices spanning all four hyperedges. A known random construction shows that the density 1/2 is best possible. This result is closely related to a question of Erdős, whether every weakly quasirandom 3-uniform hypergraph H with density bigger than 1/2, i.e., every large subset of vertices induces a hypergraph with density bigger than 1/2, contains a tetrahedron.