Article ID Journal Published Year Pages File Type
5777009 Discrete Mathematics 2017 7 Pages PDF
Abstract
For a hypergraph H, let δ1(H) denote the minimum vertex degree of H, and ν(H) denote the maximum size of a matching in H. For integers n≥m≥1, let d3(n,m)=n2−(n−⌊m∕3⌋)(n−⌊(m+1)∕3⌋)ifm≠1(mod3),n2−(n−(m−1)∕3)2+1if m=1(mod3).Let H be a 3-partite 3-uniform hypergraph with n vertices in each partition class. Lo and Markström proved that there exists a positive integer N such that if n≥N and δ1(H)>d3(n,n−1), then ν(H)>n−1. They also showed that if n≥37m and δ1(H)>d3(n,m), then ν(H)>m, and asked whether the condition n≥37m can be replaced by n>m. In this note, we show that there exists a positive integer n0 such that if n≥n0 and δ1(H)>d3(n,m), then ν(H)>m.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,