Circuitos hamiltonianos e problemas de ladrilhamento em hipergrafos

• Processo: 14/18641-5
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Vigência (Início): 01 de março de 2015
• Vigência (Término): 18 de agosto de 2018
• Área do conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Matemática da Computação
• Pesquisador responsável: Yoshiharu Kohayakawa
• Beneficiário: Jie Han
• Instituição Sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Vinculado ao auxílio: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação, AP.TEM
• Bolsa(s) vinculada(s): 15/07869-8 - Emparelhamento perfeitos e ladrilhamentos em hipergrafos, BE.EP.PD
• Assunto(s): Combinatória Problemas extremais
• Palavra(s)-Chave do Pesquisador: circuitos hamiltonianos | Hipergrafos | Ladrilhamento | método da regularidade | números de Ramsey | Problemas extremais | Combinatória

Resumo

Este é o projeto de pesquisa para a estadia de Jie Han no Instituto de Matemática e Estatística da Universidade de São Paulo (IME/USP), inicialmente planejada para o período de 1/2/2015 a 31/1/2017 (2 anos). Este pesquisador será membro do grupo de pesquisa em combinatória e em teoria da computação do IME/USP, e também será membro do NUMEC, Núcleo de Modelagem Estocástica e Complexidade, um núcleo de apoio à pesquisa da Pró-reitoria de Pesquisa da USP.Propõe-se a investigação de duas classes de problemas da teoria de grafos e hipergrafos e uma terceira coleção de problemas extremais relacionados. Mais especificamente, são apresentados problemas envolvendo os seguintes tópicos: (i) existência de circuitos hamiltonianos em hipergrafos com limitações de grau, (ii) existência de ladrilhamentos em hipergrafos com limitações de grau e (iii) estruturas geradoras em grafos e hipergrafos pseudo-aleatórios e outros problemas extremais.

Publicações científicas

(28)

(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)

HAN, JIE. DECISION PROBLEM FOR PERFECT MATCHINGS IN DENSE k-UNIFORM HYPERGRAPHS. Transactions of the American Mathematical Society, v. 369, n. 7, p. 5197-5218, JUL 2017. (14/18641-5, 15/07869-8)

HAN, JIE; ZHAO, YI. Forbidding Hamilton cycles in uniform hypergraphs. JOURNAL OF COMBINATORIAL THEORY SERIES A, v. 143, p. 107-115, OCT 2016. (15/07869-8, 14/18641-5)

HAN, JIE; KOHAYAKAWA, YOSHIHARU. THE MAXIMUM SIZE OF A NON-TRIVIAL INTERSECTING UNIFORM FAMILY THAT IS NOT A SUBFAMILY OF THE HILTON-MILNER FAMILY. Proceedings of the American Mathematical Society, v. 145, n. 1, p. 73-87, JAN 2017. (15/07869-8, 14/18641-5, 13/07699-0, 13/03447-6)

HAN, JIE. On vertex-disjoint paths in regular graphs. ELECTRONIC JOURNAL OF COMBINATORICS, v. 25, n. 2, APR 27 2018. (13/03447-6, 14/18641-5)

HAN, JIE; LO, ALLAN; TREGLOWN, ANDREW; ZHAO, YI. Exact Minimum Codegree Threshold for K-4(-)-Factors. COMBINATORICS PROBABILITY & COMPUTING, v. 26, n. 6, p. 856-885, NOV 2017. (14/18641-5, 13/03447-6)

CHEN, GUANTAO; HAN, JIE; SUIL, O.; SHAN, SONGLING; TSUCHIYA, SHOICHI. Forbidden Pairs and the Existence of a Spanning Halin Subgraph. GRAPHS AND COMBINATORICS, v. 33, n. 5, p. 1321-1345, SEP 2017. (14/18641-5, 15/07869-8)

GAO, WEI; HAN, JIE. Minimum Codegree Threshold for C-6(3)-Factors in 3-Uniform Hypergraphs. COMBINATORICS PROBABILITY & COMPUTING, v. 26, n. 4, p. 536-559, JUL 2017. (14/18641-5, 15/07869-8, 13/03447-6)

HAN, JIE. PERFECT MATCHINGS IN HYPERGRAPHS AND THE ERDOS MATCHING CONJECTURE. SIAM JOURNAL ON DISCRETE MATHEMATICS, v. 30, n. 3, p. 1351-1357, 2016. (14/18641-5, 15/07869-8)

HAN, JIE; KOHAYAKAWA, YOSHIHARU; PERSON, YURY. ear-perfect clique-factors in sparse pseudorandom graph. COMBINATORICS PROBABILITY & COMPUTING, v. 30, n. 4, p. 570-590, JUL 2021. (18/04876-1, 13/03447-6, 14/18641-5)

BASTOS, JOSEFRAN DE OLIVEIRA; BENEVIDES, FABRICIO SIQUEIRA; HAN, JIE. The number of Gallai k-colorings of complete graphs. JOURNAL OF COMBINATORIAL THEORY SERIES B, v. 144, p. 1-13, SEP 2020. (14/18641-5)

HAN, JIE; LO, ALLAN; SANHUEZA-MATAMALA, NICOLAS. Covering and tiling hypergraphs with tight cycles. COMBINATORICS PROBABILITY & COMPUTING, v. 30, n. 2, p. 288-329, MAR 2021. (14/18641-5, 13/03447-6, 15/07869-8)

HAN, JIE; ZANG, CHUANYUN; ZHAO, YI. Matchings in k-partite k-uniform hypergraphs. JOURNAL OF GRAPH THEORY, v. 95, n. 1, NOV 2019. (15/07869-8, 13/03447-6, 14/18641-5)

HAN, JIE; ZANG, CHUANYUN; ZHAO, YI. Minimum vertex degree thresholds for tiling complete 3-partite 3-graphs. JOURNAL OF COMBINATORIAL THEORY SERIES A, v. 149, p. 115-147, JUL 2017. (14/18641-5, 13/03447-6, 15/07869-8)

FRANKL, PETER; HAN, JIE; HUANG, HAO; ZHAO, YI. A degree version of the Hilton-Milner theorem. JOURNAL OF COMBINATORIAL THEORY SERIES A, v. 155, p. 493-502, APR 2018. (14/18641-5, 13/03447-6)

HAN, JIE; KOHAYAKAWA, YOSHIHARU; SALES, MARCELO TADEU; STAGNI, HENRIQUE; BENDER, MA; FARACHCOLTON, M; MOSTEIRO, MA. Property Testing for Point Sets on the Plane. LATIN 2018: THEORETICAL INFORMATICS, v. 10807, p. 13-pg., 2018-01-01. (13/07699-0, 15/15986-4, 14/18641-5, 13/03447-6)

HAN, JIE; KOHAYAKAWA, YOSHIHARU; MORRIS, PATRICK; PERSON, YURY. Finding any given 2-factor in sparse pseudorandom graphs efficiently. JOURNAL OF GRAPH THEORY, v. 96, n. 1, SI, MAY 2020. (13/03447-6, 14/18641-5)

HAN, JIE. ON PERFECT MATCHINGS AND TILINGS IN UNIFORM HYPERGRAPHS. SIAM JOURNAL ON DISCRETE MATHEMATICS, v. 32, n. 2, p. 919-932, 2018. (13/03447-6, 14/18641-5)

HAN, JIE; TREGLOWN, ANDREW. The complexity of perfect matchings and packings in dense hypergraphs. JOURNAL OF COMBINATORIAL THEORY SERIES B, v. 141, p. 72-104, MAR 2020. (13/03447-6, 15/07869-8, 14/18641-5)

HAN, JIE; GOPAL, TV; JAGER, G; STEILA, S. The Complexity of Perfect Packings in Dense Graphs. THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2017), v. 10185, p. 15-pg., 2017-01-01. (14/18641-5, 15/07869-8, 13/03447-6)

HAN, JIE. DECISION PROBLEM FOR PERFECT MATCHINGS IN DENSE k-UNIFORM HYPERGRAPHS. TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, v. 369, n. 7, p. 22-pg., 2017-07-01. (14/18641-5, 15/07869-8)

GAO, WEI; HAN, JIE; ZHAO, YI. Codegree Conditions for Tiling Complete k-Partite k-Graphs and Loose Cycles. COMBINATORICS PROBABILITY & COMPUTING, v. 28, n. 6, p. 840-870, NOV 2019. (14/18641-5, 15/07869-8, 13/03447-6)

HAN, JIE; KOHAYAKAWA, YOSHIHARU; MORRIS, PATRICK; PERSON, YURY. Finding any given 2-factor in sparse pseudorandom graphs efficiently. JOURNAL OF GRAPH THEORY, v. 96, n. 1, p. 22-pg., 2020-05-05. (14/18641-5, 13/03447-6)

HAN, JIE; ZHAO, YI. Hamiltonicity in randomly perturbed hypergraphs. JOURNAL OF COMBINATORIAL THEORY SERIES B, v. 144, p. 14-31, SEP 2020. (14/18641-5)

HAN, JIE; KIM, JAEHOON. Two-regular subgraphs of odd-uniform hypergraphs. JOURNAL OF COMBINATORIAL THEORY SERIES B, v. 128, p. 175-191, JAN 2018. (13/03447-6, 14/18641-5, 15/07869-8)

HAN, JIE. NEAR PERFECT MATCHINGS IN k-UNIFORM HYPERGRAPHS II. SIAM JOURNAL ON DISCRETE MATHEMATICS, v. 30, n. 3, p. 1453-1469, 2016. (14/18641-5, 15/07869-8)

HAN, JIE; KOHAYAKAWA, YOSHIHARU; MORRIS, PATRICK; PERSON, YURY. Clique-factors in sparse pseudorandom graphs. EUROPEAN JOURNAL OF COMBINATORICS, v. 82, DEC 2019. (13/03447-6, 14/18641-5)

HAN, JIE; KOHAYAKAWA, YOSHIHARU. On hypergraphs without loose cycles. DISCRETE MATHEMATICS, v. 341, n. 4, p. 946-949, APR 2018. (14/18641-5, 13/07699-0, 13/03447-6)

BEDENKNECHT, WIEBKE; HAN, JIE; KOHAYAKAWA, YOSHIHARU; MOTA, GUILHERME O.. Powers of tight Hamilton cycles in randomly perturbed hypergraphs. RANDOM STRUCTURES & ALGORITHMS, v. 55, n. 4, JULY 2019. (14/18641-5, 13/03447-6, 18/04876-1)