Covering and tiling hypergraphs with tight cycles

Autor(es)

Han, Jie ^[1] ; Lo, Allan ^[2] ; Sanhueza-Matamala, Nicolas ^[2]

Afiliação do(s) autor(es)

^[1] Univ Rhode Isl, Dept Math, Kingston, RI 02881 - USA

^[2] Univ Birmingham, Sch Math, Birmingham B15 2TT, W Midlands - England

• Tipo de documento: Artigo Científico
• Fonte: COMBINATORICS PROBABILITY & COMPUTING; v. 30, n. 2, p. 288-329, MAR 2021.
• Citações Web of Science: 0

Resumo

A k-uniform tight cycle C-s(k) is a hypergraph on s > k vertices with a cyclic ordering such that every k consecutive vertices under this ordering form an edge. The pair (k, s) is admissible if gcd (k, s) = 1 or k / gcd (k,s) is even. We prove that if s >= 2k(2) and H is a k-uniform hypergraph with minimum codegree at least (1/2 + o(1))|V(H)|, then every vertex is covered by a copy of C-s(k). The bound is asymptotically sharp if (k, s) is admissible. Our main tool allows us to arbitrarily rearrange the order in which a tight path wraps around a complete k-partite k-uniform hypergraph, which may be of independent interest. For hypergraphs F and H, a perfect F-tiling in H is a spanning collection of vertex-disjoint copies of F. For k >= 3, there are currently only a handful of known F-tiling results when F is k-uniform but not k-partite. If s not equivalent to 0 mod k, then C-s(k) is not k-partite. Here we prove an F-tiling result for a family of non-k-partite k-uniform hypergraphs F. Namely, for s >= 5k(2), every k-uniform hypergraph H with minimum codegree at least (1/2 + 1/(2s) + o(1))|V(H)| has a perfect C-s(k)-tiling. Moreover, the bound is asymptotically sharp if k is even and (k, s) is admissible. (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: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
• Beneficiário: Carlos Eduardo Ferreira
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• 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