Matchings in k-partite k-uniform hypergraphs

DOI10.1002/JGT.22527zbMATH Open1486.05216arXiv1611.00290OpenAlexW2991501373MaRDI QIDQ5066909FDOQ5066909

Authors: Jie Han, C. Zang, Yi Zhao 

Publication date: 31 March 2022

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: For $kge3$ and $epsilon>0$, let $H$ be a $k$-partite $k$-graph with parts $V_1,dots,V_k$ each of size $n$, where $n$ is sufficiently large. Assume that for each $iin[k]$, every $(k-1)$-set in $pro{d}_{jin[k]setminusi}{V}_i$ lies in at least $a_i$ edges, and $a_{1}ge{a}_{2}gecdotsge{a}_k$. We show that if $a_1,a_{2}geepsilonn$, then $H$ contains a matching of size $minn-1,su{m}_{iin[k]}{a}_i$. In particular, $H$ contains a matching of size $n-1$ if each crossing $(k-1)$-set lies in at least $lceiln/kceil$ edges, or each crossing $(k-1)$-set lies in at least $lfloorn/kfloor$ edges and $$. This special case answers a question of R"odl and Ruci'nski and was independently obtained by Lu, Wang, and Yu. The proof of Lu, Wang, and Yu closely follows the approach of Han [Combin. Probab. Comput. 24 (2015), 723--732] by using the absorbing method and considering an extremal case. In contrast, our result is more general and its proof is thus more involved: it uses a more complex absorbing method and deals with two extremal cases.

Full work available at URL: https://arxiv.org/abs/1611.00290

Recommendations

• Perfect matching in \(k\)-partite \(k\)-graphs and 3-uniform HM-bipartite hypergraphs
• Near perfect matchings in \(k\)-uniform hypergraphs
• Perfect matchings in large uniform hypergraphs with large minimum collective degree
• Nearly perfect matchings in uniform hypergraphs
• Matching of given sizes in hypergraphs

zbMATH Keywords

matchingabsorbing methodhypergraph

Mathematics Subject Classification ID

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (10)

• Network Capacity Bound for Personalized PageRank in Multimodal Networks
• Perfect matching in \(k\)-partite \(k\)-graphs and 3-uniform HM-bipartite hypergraphs
• Matching and domination numbers in \(r\)-uniform hypergraphs
• Almost perfect matchings in \(k\)-partite \(k\)-graphs
• The $r$-matching sequencibility of complete multi-$k$-partite $k$-graphs
• A generalization of Hall's theorem for \(k\)-uniform \(k\)-partite hypergraphs
• The asymptotic induced matching number of hypergraphs: balanced binary strings
• An existence theorem of perfect matching on \(k\)-partite \(k\)-uniform hypergraphs via distance spectral radius
• Near Perfect Matchings in ${k}$-Uniform Hypergraphs II
• Maximally connected \(p\)-partite uniform hypergraphs

This page was built for publication: Matchings in \(k\)-partite \(k\)-uniform hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5066909)