Matchings in k-partite k-uniform hypergraphs

DOI10.1002/JGT.22527MaRDI QIDQ5066909zbMATH OpenOpenAlexFDO

Authors Jie Han, C. Zang, Yi Zhao

Publication date 31 March 2022

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

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

zbMATH Keywords

matchingabsorbing methodhypergraph

Mathematics Subject Classification ID

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

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.

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

Cited in

(10)

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

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)