Perfect Matching in k -partite k -graphs and 3-uniform HM-bipartite Hypergraphs
- PDF / 142,791 Bytes
- 6 Pages / 612 x 792 pts (letter) Page_size
- 93 Downloads / 193 Views
Acta Mathemacae Applicatae Sinica, English Series The Editorial Office of AMAS & Springer-Verlag GmbH Germany 2020
Perfect Matching in k-partite k-graphs and 3-uniform HM-bipartite Hypergraphs Chun-qiu FANG, Mei LU† Department of Mathematical Sciences, Tsinghua University, Beijing 100084, China (E-mail: [email protected], † [email protected])
Abstract
Let H = (V, E) be an n-balanced k-partite k-graph with partition classes V1 , . . . , Vk . Suppose for
every legal (k − 1)-tuple f contained in V \ V1 and for every legal (k − 1)-tuple g contained in V \ Vk such that f ∪ g ̸∈ E(H), we have d(f ) + d(g) ≥ n + 1. In this paper, we prove that under this condition H must have a perfect matching. Another result of this paper is about the perfect matching in 3-uniform hm-bipartite hypergraphs. Let G be a 3-uniform hm-bipartite hypergraph with one of whose sides V1 has the size n, the another side V2 has size 2n. If for all the legal 2-tuple f with |f ∩ V1 | = 1 and for all the legal 2-tuple g with |g ∩ V1 | = 0, we have d(f ) ≥ n − 2 and d(g) >
Keywords
then G has a perfect matching.
Perfect matching; k-partite k-graph; hm-bipartite hypergraph
2000 MR Subject Classification
1
n , 2
05C70; 05C65; 68R10
Introduction
The so-called ‘marriage theorem’ of Hall provides a necessary and sufficient condition for the existence of a perfect matching in a bipartite graph. A well-known theorem of [17] gives a characterisation of all those graphs which contain a perfect matching and there are efficient algorithms (e.g.,Edmond’s algorithm[4] ) which decide whether a graph contains a perfect matching. For hypergraphs, there are only partial results which are analog of Hall Theorem for the existence of a perfect matching (see [3] and [7]). From an algorithmic point of view, there is also a major difference between matching problems for graphs and hypergraphs. In fact, Karp[9] proved that one can not find a maximum matching in an r-partite r-uniform hypergraph in polynomial time unless P = N P where r ≥ 3. Therefore, it is interesting to find necessary or sufficient conditions that guarantee a perfect matching in hypergraphs (see [5, 6, 10–16]). A k-uniform hypergraph (also called k-graph) is a pair H = (V, E), where V := V (H) is a ( ) finite set of vertices and E := E(H) ⊆ Vk is a family of k-element subsets of V . A matching in H is a set of pairwise disjoint edges of H. We call matching M a perfect matching in H, if M covers every vertex of H. ( ) Given a k-uniform hypergraph H = (V, E) and a set S = {v1 , · · · , vl } ∈ Vl , 1 ≤ l ≤ k − 1, let d(S) := d(v1 , · · · , vl ) denote the number of edges in H containing the set S. In this paper, we prove the sufficient conditions for the existence of a perfect matching in a k-partite k-graph Manuscript received September 29, 2018. Accepted on June 17, 2019. This paper is supported in part by the National Natural Science Foundation of China (No. 61373019). † Corresponding author.
Perfect Matching in k-partite k-graphs and 3-uniform HM-bipartite Hypergraphs
637
a
Data Loading...
