Busca avançada
Ano de início
Entree
Conteúdo relacionado
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

ON PERFECT MATCHINGS AND TILINGS IN UNIFORM HYPERGRAPHS

Texto completo
Autor(es):
Han, Jie
Número total de Autores: 1
Tipo de documento: Artigo Científico
Fonte: SIAM JOURNAL ON DISCRETE MATHEMATICS; v. 32, n. 2, p. 919-932, 2018.
Citações Web of Science: 0
Resumo

In this paper we study some variants of Dirac-type problems in hypergraphs. First, we show that for k >= 3, if H is a k-graph on n is an element of kN vertices with independence number at most n/p and minimum codegree at least (1/p + o(1))n, where p is the smallest prime factor of k, then H contains a perfect matching. Second, we show that if H is a 3-graph on n is an element of 3N vertices which does not contain any induced copy of K-4(-) (the unique 3-graph with 4 vertices and 3 edges) and has minimum codegree at least (1/3 + o(1))) n, then H contains a perfect matching. Moreover, if we allow the matching to miss at most 3 vertices, then the minimum degree condition can be reduced to (1/6 + o(1)))n. Third, we show that if H is a 3-graph on n is an element of 4N vertices which does not contain any induced copy of K-4(-) and has minimum codegree at least (1/8 + o(1))) n, then H contains a perfect Y-tiling, where Y represents the unique 3-graph with 4 vertices and 2 edges. We also provide the examples showing that our minimum codegree conditions are asymptotically best possible. Our main tool for finding the perfect matching is a characterization theorem in {[}J. Han, Trans. Amer. Math. Soc., 369 (2017), pp. 5197-5218] that characterizes the k-graphs with minimum codegree at least n/k which contain a perfect matching. (AU)

Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
Beneficiário:Carlos Eduardo Ferreira
Linha de fomento: Auxílio à Pesquisa - Temático
Processo FAPESP: 14/18641-5 - Circuitos Hamiltonianos e problemas de ladrilhamento em hipergrafos
Beneficiário:Jie Han
Linha de fomento: Bolsas no Brasil - Pós-Doutorado