Problemas de imersão e empacotamento em teoria extremal dos grafos

• Processo: 09/17831-7
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Data de Início da vigência: 01 de abril de 2010
• Data de Término da vigência: 31 de dezembro de 2011
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Matemática da Computação
• Pesquisador responsável: Yoshiharu Kohayakawa
• Beneficiário: Julia Boettcher
• Instituição Sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Palavra(s)-Chave do Pesquisador: conjectura de Gyárfás e Lehel | Empacotamento de Grafos | imersão de grafos | método da regularidade | resiliência de grafos | Teoria extremal dos grafos | Combinatória, algoritmos, teoria da computação

Resumo

Este é um projeto de pesquisa para a solicitação de uma bolsa de pós-doutoramento. Trata-se de uma bolsa que solicitamos para a estadia de Julia Böttcher no Instituto de Matemática e Estatística da Universidade de São Paulo (IME/USP) no período de 1/4/2010 a 31/3/2012 (2 anos). Esta pesquisadora já é pós-doutora nesta instituição, com bolsa da Comunidade Européia, através do programa EUBRANEX; a vigência desta bolsa é de 1/10/2009 a 31/3/2010 (6 meses).A candidata é membro ativo do NUMEC, Núcleo de Modelagem Estatística e Complexidade, um núcleo de pesquisa de apoio à pesquisa da Pró-reitoria de Pesquisa da USP.A pesquisa proposta é centrada em três vertentes de pesquisa da área de teoria extremal dos grafos: (i) problemas de imersão de grafos grandes em grafos densos, (ii) problemas de imersão e resiliência para grafos geradores e grafos quase-geradores em grafos aleatórios esparsos, e (iii) problemas de empacotamento para árvores.

Publicações científicas

(14)

(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)

ALLEN, PETER; BOETTCHER, JULIA; GRIFFITHS, SIMON; KOHAYAKAWA, YOSHIHARU; MORRIS, ROBERT. The chromatic thresholds of graphs. ADVANCES IN MATHEMATICS, v. 235, p. 261-295, MAR 1 2013. (09/17831-7, 10/09555-7)

BOETTCHER, JULIA; FONIOK, JAN. Ramsey Properties of Permutations. ELECTRONIC JOURNAL OF COMBINATORICS, v. 20, n. 1, JAN 7 2013. (09/17831-7)

ALLEN, PETER; BOTTCHER, JULIA; GRIFFITHS, SIMON; KOHAYAKAWA, YOSHIHARU; MORRIS, ROBERT. Chromatic Thresholds in Dense Random Graphs. RANDOM STRUCTURES & ALGORITHMS, v. 51, n. 2, p. 185-214, SEP 2017. (13/03447-6, 09/17831-7, 10/09555-7, 13/07699-0)

ALLEN, PETER; BOETTCHER, JULIA; HLADKY, JAN; PIGUET, DIANA. An extension of Turan's Theorem, uniqueness and stability. ELECTRONIC JOURNAL OF COMBINATORICS, v. 21, n. 4, OCT 2 2014. (09/17831-7, 10/09555-7)

ALLEN, PETER; BOETTCHER, JULIA; HLADKY, JAN; PIGUET, DIANA. A Density Corradi-Hajnal Theorem. CANADIAN JOURNAL OF MATHEMATICS-JOURNAL CANADIEN DE MATHEMATIQUES, v. 67, n. 4, p. 721-758, AUG 2015. (09/17831-7, 10/09555-7)

ALLEN, PETER; BOTTCHER, JULIA; HAN, HIEP; KOHAYAKAWA, YOSHIHARU; PERSON, YURY. POWERS OF HAMILTON CYCLES IN PSEUDORANDOM GRAPHS. COMBINATORICA, v. 37, n. 4, p. 573-616, AUG 2017. (10/16526-3, 09/17831-7, 13/07699-0, 10/09555-7, 13/03447-6)

ALLEN, PETER; BOETTCHER, JULIA; KOHAYAKAWA, YOSHIHARU; PERSON, YURY. Tight Hamilton Cycles in Random Hypergraphs. RANDOM STRUCTURES & ALGORITHMS, v. 46, n. 3, p. 446-465, MAY 2015. (09/17831-7, 13/07699-0, 13/03447-6, 10/09555-7)

ALLEN, PETER; BOETTCHER, JULIA; HAN, HIEP; KOHAYAKAWA, YOSHIHARU; PERSON, YURY; PARDO, A; VIOLA, A. Powers of Hamilton Cycles in Pseudorandom Graphs. LATIN 2014: THEORETICAL INFORMATICS, v. 8392, p. 12-pg., 2014-01-01. (09/17831-7, 13/07699-0, 10/16526-3, 13/03447-6, 10/09555-7)

BOETTCHER, JULIA; KOHAYAKAWA, YOSHIHARU; PROCACCI, ALDO. Properly coloured copies and rainbow copies of large graphs with small maximum degree. RANDOM STRUCTURES & ALGORITHMS, v. 40, n. 4, p. 425-436, JUL 2012. (09/17831-7)

ALLEN, PETER; BOTTCHER, JULIA; COOLEY, OLIVER; MYCROFT, RICHARD. Tight cycles and regular slices in dense hypergraphs. JOURNAL OF COMBINATORIAL THEORY SERIES A, v. 149, p. 30-100, JUL 2017. (10/09555-7, 09/17831-7)

ALLEN, PETER; BOTTCHER, JULIA; GRIFFITHS, SIMON; KOHAYAKAWA, YOSHIHARU; MORRIS, ROBERT. Chromatic Thresholds in Sparse Random Graphs. RANDOM STRUCTURES & ALGORITHMS, v. 51, n. 2, p. 215-236, SEP 2017. (09/17831-7, 13/07699-0, 13/03447-6, 10/09555-7)

BOETTCHER, JULIA; TARAZ, ANUSCH; WUERFL, ANDREAS. Perfect Graphs of Fixed Density: Counting and Homogeneous Sets. COMBINATORICS PROBABILITY & COMPUTING, v. 21, n. 5, p. 661-682, SEP 2012. (09/17831-7)

ALLEN, PETER; BOETTCHER, JULIA; PERSON, YURY. An improved error term for minimum H-decompositions of graphs. JOURNAL OF COMBINATORIAL THEORY SERIES B, v. 108, p. 92-101, SEP 2014. (09/17831-7, 10/09555-7)

ALLEN, PETER; BOETTCHER, JULIA; HLADKY, JAN; PIGUET, DIANA. Turannical hypergraphs. RANDOM STRUCTURES & ALGORITHMS, v. 42, n. 1, p. 29-58, JAN 2013. (09/17831-7, 10/09555-7)