Regular subgraphs of uniform hypergraphs

详细信息    查看全文

• 作者：Jaehoon Kim¹ ; ^{j.kim.3@bham.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; ^{mutualteon@gmail.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Matchings ; Hypergraphs ; Regular subgraphs ; Stability
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2016
• 出版时间：July 2016
• 年：2016
• 卷：119
• 期：Complete
• 页码：214-236
• 全文大小：453 K

文摘

We prove that for every integer 16000265&_mathId=si1.gif&_user=111111111&_pii=S0095895616000265&_rdoc=1&_issn=00958956&md5=eba6d66aa8f959c090d5a3400b6d119b" title="Click to view the MathML source">r≥2$r\ge 2$, an n-vertex k-uniform hypergraph H containing no r  -regular subgraphs has at most 16000265&_mathId=si2.gif&_user=111111111&_pii=S0095895616000265&_rdoc=1&_issn=00958956&md5=24adb61b7879eeba4d5bf8150225f21c">16000265-si2.gif">$(1+o(1))\left(\begin{array}{c}n-1\\ k-1\end{array}\right)$ edges if 16000265&_mathId=si25.gif&_user=111111111&_pii=S0095895616000265&_rdoc=1&_issn=00958956&md5=66cb47802eecadda4521070e4a60462e" title="Click to view the MathML source">k≥r+1$k\ge r+1$ and n   is sufficiently large. Moreover, if 16000265&_mathId=si32.gif&_user=111111111&_pii=S0095895616000265&_rdoc=1&_issn=00958956&md5=b391f054b3ad8c6700fd207474174dc1" title="Click to view the MathML source">r∈{3,4}$r\in \{3,4\}$, 16000265&_mathId=si34.gif&_user=111111111&_pii=S0095895616000265&_rdoc=1&_issn=00958956&md5=a06bd7996a48ac8df7e6458c19315755" title="Click to view the MathML source">r|k$r|k$ and k, n are both sufficiently large, then the maximum number of edges in an n-vertex k-uniform hypergraph containing no r  -regular subgraphs is exactly 16000265&_mathId=si16.gif&_user=111111111&_pii=S0095895616000265&_rdoc=1&_issn=00958956&md5=1d1d4cbae9f6aaf411445511329f7e94">16000265-si16.gif">$\left(\begin{array}{c}n-1\\ k-1\end{array}\right)$, with equality only if all edges contain a specific vertex v. We also ask some related questions.