NEAR PERFECT MATCHINGS IN k-UNIFORM HYPERGRAPHS II

Autor(es)

Han, Jie

• Tipo de documento: Artigo Científico
• Fonte: SIAM JOURNAL ON DISCRETE MATHEMATICS; v. 30, n. 3, p. 1453-1469, 2016.
• Citações Web of Science: 1

Resumo

Suppose k inverted iota n and H is an n-vertex k-uniform hypergraph. A near perfect matching in H is a matching of size left perpendicularn/kright perpendicular. We give a divisibility barrier construction that prevents the existence of near perfect matchings in H. This generalizes the divisibility barrier for perfect matchings. We give a conjecture on the minimum d-degree threshold forcing a (near) perfect matching in H which generalizes a well-known conjecture on perfect matchings. We also verify our conjecture for various cases. Our proof makes use of the lattice-based absorbing method that we used recently to solve two other problems on matching and tilings for hypergraphs. (AU)

• Processo FAPESP: 14/18641-5 - Circuitos hamiltonianos e problemas de ladrilhamento em hipergrafos
• Beneficiário: Jie Han
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Processo FAPESP: 15/07869-8 - Emparelhamento perfeitos e ladrilhamentos em hipergrafos
• Beneficiário: Jie Han
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Pós-Doutorado