Perfect matchings in 4-uniform hypergraphs

详细信息    查看全文

• 作者：Imdadullah Khan ^{imdad.khan@lums.edu.pk" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Hypergraphs ; Perfect matching ; Vertex degree
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：116
• 期：Complete
• 页码：333-366
• 全文大小：761 K

文摘

A perfect matching in a 4-uniform hypergraph on n   vertices is a subset of class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895615001124&_mathId=si1.gif&_user=111111111&_pii=S0095895615001124&_rdoc=1&_issn=00958956&md5=5e8f64415986a2580726a9f4fb4ed872">class="imgLazyJSB inlineImage" height="18" width="24" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0095895615001124-si1.gif">class="mathContainer hidden">class="mathCode">$\lfloor \frac{n}{4}\rfloor$ disjoint edges. We prove that if H   is a sufficiently large 4-uniform hypergraph on class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895615001124&_mathId=si2.gif&_user=111111111&_pii=S0095895615001124&_rdoc=1&_issn=00958956&md5=93973555ed8fa9490e3a0aad8d4d3a0c" title="Click to view the MathML source">n=4kclass="mathContainer hidden">class="mathCode">$n=4k$ vertices such that every vertex belongs to more than class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895615001124&_mathId=si3.gif&_user=111111111&_pii=S0095895615001124&_rdoc=1&_issn=00958956&md5=8233f3460bf2db10468291c587087b29">class="imgLazyJSB inlineImage" height="22" width="99" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0095895615001124-si3.gif">class="mathContainer hidden">class="mathCode">$\left(\begin{array}{c}n-1\\ 3\end{array}\right)-\left(\begin{array}{c}3n/4\\ 3\end{array}\right)$ edges, then H contains a perfect matching. A construction due to Hàn, Person, and Schacht shows that this result is the best possible.