Teoria de Ramsey, teoria estrutural de grafos e aplicações em Bioinformática

• Processo: 18/04876-1
• Modalidade de apoio: Auxílio à Pesquisa - Jovens Pesquisadores
• Vigência: 01 de outubro de 2018 - 30 de setembro de 2022
• Área do conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Matemática da Computação
• Pesquisador responsável: Guilherme Oliveira Mota
• Beneficiário: Guilherme Oliveira Mota
• Instituição Sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Auxílios(s) vinculado(s): 21/11020-9 - Subestruturas de grandes proporções em grafos e hipergrafos, AV.EXT
• Bolsa(s) vinculada(s): 21/09306-1 - Propriedades anti-Ramsey: não-existência de cópias multicoloridas, BP.IC; 21/09286-0 - Partições monocromáticas de grafos completos, BP.IC; 20/03336-3 - Propriedades estruturais e extremais de grafos e hipergrafos, BP.DR; + mais bolsas vinculadas 20/10796-0 - Problemas estruturais em grafos aleatórios, BP.PD; 20/08252-2 - Problemas extremais e probabilísticos em coloração de grafos, BP.PD; 19/27350-8 - Partição de grafos aleatórios em cópias monocromáticas, BP.MS; 19/15048-5 - Funções limiares para propriedades anti-Ramsey, BP.MS; 19/04375-5 - Problemas em Teoria de Ramsey, grafos aleatórios e imersões, BP.PD; 19/00299-2 - Comparação de métodos de detecção de motifs em redes biológicas, BP.IC; 18/22768-1 - Estruturas Ramsey e anti-Ramsey em grafos aleatórios e determinísticos, BP.DR; 19/02087-2 - Propriedades anti-Ramsey: encontrando cópias multicoloridas, BP.IC - menos bolsas vinculadas
• Assunto(s): Combinatória Biologia computacional Teoria dos grafos
• Palavra(s)-Chave do Pesquisador: coloração | Decomposição | grafos | Grafos Aleatórios | Partição de grafos | Ramsey | Combinatória

Resumo

Este é o projeto de pesquisa para o auxílio jovens pesquisadores em centro emergente a ser desenvolvido no Centro de Matemática, Computação e Cognição (CMCC) da Universidade Federal do ABC (UFABC) no período de 1/8/2018 a 31/7/2022 (48 meses). A Ciência da Computação está presente em diversas áreas do conhecimento, de modo que a necessidade de lidar com problemas cada vez mais complexos exige o desenvolvimento de novas tecnologias. Tal fenômeno tem gerado uma demanda por novas técnicas e avanços em Ciência da Computação. Importantes avanços tecnológicos não são possíveis sem resultados teóricos consistentes que sirvam de base para eles. Por exemplo, áreas como a Bioinformática tem se beneficiado da aplicação de técnicas combinatórias e da investigação de propriedades estruturais de grafos. Este projeto tem dois objetivos principais: (i) Investigar características estruturais e algorítmicas de grafos e estruturas relacionadas; (ii) aplicar a teoria dos grafos em problemas na área de Bioinformática através de uma abordagem interdisciplinar. Progressos no primeiro dos objetivos deve fornecer novas estratégias para problemas relacionados, bem como disponibilizar novas técnicas para problemas em diversas áreas do conhecimento. Um estudo de variadas técnicas combinatórias e um bom entendimento de propriedades estruturais de grafos são os pilares deste projeto. A equipe proposta contém um misto de jovens pesquisadores com excelente desempenho acadêmico e pesquisadores renomados que possuem bastante experiência nos problemas a serem investigados. Esperamos que este projeto consolide a formação de um grupo de pesquisa na área de combinatória e teoria de grafos na UFABC, bem como aumente a sinergia entre os pesquisadores participantes do projeto. Ademais, o projeto vai contribuir para o fortalecimento da inserção nacional e internacional da universidade. As contribuições científicas do projeto se darão com a publicação de artigos científicos em importantes periódicos de alta circulação e com a apresentação de trabalhos em conferências internacionais. (AU)

Publicações científicas

(31)

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

NAIA, TASSIO. Trees contained in every orientation of a graph. ELECTRONIC JOURNAL OF COMBINATORICS, v. 29, n. 2, p. 5-pg., 2022-05-06. (19/04375-5, 18/04876-1, 19/13364-7)

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)

BERGER, S.; KOHAYAKAWA, Y.; MAESAKA, G. S.; MARTINS, T.; MENDONCA, W.; MOTA, G. O.; PARCZYK, O.. THE SIZE-RAMSEY NUMBER OF POWERS OF BOUNDED DEGREE TREES. ACTA MATHEMATICA UNIVERSITATIS COMENIANAE, v. 88, n. 3, p. 451-456, 2019. (13/03447-6, 18/04876-1)

KOHAYAKAWA, Y.; MENDONCA, W.; MOTA, G.; SCHUELKE, B.. COVERING 3-COLOURED RANDOM GRAPHS WITH MONOCHROMATIC TREES. ACTA MATHEMATICA UNIVERSITATIS COMENIANAE, v. 88, n. 3, p. 871-875, 2019. (13/03447-6, 18/04876-1)

BASTOS, JOSEFRAN DE OLIVEIRA; MOTA, GUILHERME OLIVEIRA; SCHACHT, MATHIAS; SCHNITZER, JAKOB; SCHULENBURG, FABIAN. LOOSE HAMILTONIAN CYCLES FORCED BY LARGE (k-2)-DEGREE - SHARP VERSION. CONTRIBUTIONS TO DISCRETE MATHEMATICS, v. 13, n. 2, p. 88-100, 2018. (13/11431-2, 18/04876-1, 13/20733-2)

BARROS, GABRIEL FERREIRA; CAVALAR, BRUNO PASQUALOTTO; KOHAYAKAWA, YOSHIHARU; NAIA, TASSIO. ORIENTATION RAMSEY THRESHOLDS FOR CYCLES AND CLIQUES. SIAM JOURNAL ON DISCRETE MATHEMATICS, v. 35, n. 4, p. 2844-2857, 2021. (19/13364-7, 18/05557-7, 18/04876-1)

BASTOS, JOSEFRAN DE OLIVEIRA; BENEVIDES, FABRICIO SIQUEIRA; MOTA, GUILHERME OLIVEIRA; SAU, IGNASI. Counting Gallai 3-colorings of complete graphs. DISCRETE MATHEMATICS, v. 342, n. 9, p. 2618-2631, SEP 2019. (18/04876-1)

COLLARES, MAURICIO; KOHAYAKAWA, YOSHIHARU; MORRIS, ROBERT; MOTA, GUILHERME O.. Counting restricted orientations of random graphs. RANDOM STRUCTURES & ALGORITHMS, JAN 2020. (13/03447-6, 18/04876-1)

BOTLER, FABIO; COLUCCI, LUCAS; KOHAYAKAWA, YOSHIHARU. The mod k chromatic index of random graphs. JOURNAL OF GRAPH THEORY, v. 103, n. 4, p. 13-pg., 2023-03-08. (18/04876-1, 20/08252-2, 15/11937-9, 19/13364-7)

BOTLER, FABIO; COLUCCI, LUCAS; KOHAYAKAWA, YOSHIHARU. The mod k chromatic index of graphs is O(k). JOURNAL OF GRAPH THEORY, v. 102, n. 1, p. 4-pg., 2022-07-30. (18/04876-1, 19/13364-7, 15/11937-9, 20/08252-2)

BOTLER, FABIO; HOPPEN, CARLOS; MOTA, GUILHERME OLIVEIRA. Counting orientations of graphs with no strongly connected tournaments. DISCRETE MATHEMATICS, v. 345, n. 12, p. 13-pg., 2022-08-05. (18/04876-1, 19/13364-7)

HOPPEN, CARLOS; KOHAYAKAWA, YOSHIHARU; LANG, RICHARD; LEFMANN, HANNO; STAGNI, HENRIQUE. ON THE QUERY COMPLEXITY OF ESTIMATING THE DISTANCE TO HEREDITARY GRAPH PROPERTIES. SIAM JOURNAL ON DISCRETE MATHEMATICS, v. 35, n. 2, p. 1238-1251, 2021. (17/02263-0, 15/15986-4, 18/04876-1)

COLLARES, MAURICIO; KOHAYAKAWA, YOSHIHARU; MARTINS, TAISA; PARENTE, ROBERTO; SOUZA, VICTOR; FERREIRA, CE; LEE, O; MIYAZAWA, FK. Hitting times for arc-disjoint arborescences in random digraph processes. PROCEEDINGS OF THE XI LATIN AND AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, v. 195, p. 9-pg., 2021-01-01. (18/04876-1)

BERGER, SOEREN; KOHAYAKAWA, YOSHIHARU; MAESAKA, GIULIA SATIKO; MARTINS, TAISA; MENDONCA, WALNER; MOTA, GUILHERME OLIVEIRA; PARCZYK, OLAF. The size-Ramsey number of powers of bounded degree trees. JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES, v. 103, n. 4, DEC 2020. (18/04876-1)

KOHAYAKAWA, YOSHIHARU; MENDONCA, WALNER; MOTA, GUILHERME OLIVEIRA; SCHUELKE, BJARNE. COVERING 3-EDGE-COLORED RANDOM GRAPHS WITH MONOCHROMATIC TREES. SIAM JOURNAL ON DISCRETE MATHEMATICS, v. 35, n. 2, p. 1447-1459, 2021. (18/04876-1, 19/13364-7)

CLEMENS, DENNIS; JENSSEN, MATTHEW; KOHAYAKAWA, YOSHIHARU; MORRISON, NATASHA; MOTA, GUILHERME OLIVEIRA; REDING, DAMIAN; ROBERTS, BARNABY. The size-Ramsey number of powers of paths. JOURNAL OF GRAPH THEORY, v. 91, n. 3, p. 290-299, JUL 2019. (13/11431-2, 18/04876-1, 13/03447-6)

KOHAYAKAWA, YOSHIHARU; LEE, SANG JUNE; MOREIRA, CARLOS GUSTAVO; RODL, VOJTECH. On strong Sidon sets of integers. JOURNAL OF COMBINATORIAL THEORY SERIES A, v. 183, OCT 2021. (18/04876-1)

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)

BOTLER, FABIO; HOPPEN, CARLOS; MOTA, GUILHERME OLIVEIRA; FERREIRA, CE; LEE, O; MIYAZAWA, FK. Counting orientations of graphs with no strongly connected tournaments. PROCEEDINGS OF THE XI LATIN AND AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, v. 195, p. 9-pg., 2021-01-01. (18/04876-1, 19/13364-7)

COLLARES, MAURICIO; KOHAYAKAWA, YOSHIHARU; MORRIS, ROBERT; MOTA, GUILHERME O.. Counting restricted orientations of random graphs. RANDOM STRUCTURES & ALGORITHMS, v. 56, n. 4, p. 1016-1030, JUL 2020. (13/03447-6, 18/04876-1)

MOTA, G. O.. THREE-COLOR BIPARTITE RAMSEY NUMBER FOR GRAPHS WITH SMALL BANDWIDTH. SIAM JOURNAL ON DISCRETE MATHEMATICS, v. 33, n. 1, p. 197-208, 2019. (18/04876-1)

CHANG, YULIN; HAN, JIE; KOHAYAKAWA, YOSHIHARU; MORRIS, PATRICK; MOTA, GUILHERME OLIVEIRA. Factors in randomly perturbed hypergraphs. RANDOM STRUCTURES & ALGORITHMS, v. 60, n. 2, JUL 2021. (19/13364-7, 18/04876-1)

KOHAYAKAWA, YOSHIHARU; MIYAZAWA, FLAVIO KEIDI; WAKABAYASHI, YOSHIKO. A tight lower bound for the online bounded space hypercube bin packing problem. DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, v. 23, n. 3, 2021. (18/04876-1, 15/11937-9, 16/01860-1)

BARROS, G. F.; CAVALAR, B. P.; MOTA, G. O.; PARCZYK, O.. Anti-Ramsey Threshold of Cycles for Sparse Graphs. ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, v. 346, p. 10-pg., 2019-08-30. (18/04876-1, 18/05557-7)

HAN, JIE; JENSSEN, MATTHEW; KOHAYAKAWA, YOSHIHARU; MOTA, GUILHERME OLIVEIRA; ROBERTS, BARNABY. The multicolour size-Ramsey number of powers of paths. JOURNAL OF COMBINATORIAL THEORY SERIES B, v. 145, p. 17-pg., 2020-11-01. (18/04876-1)

HOPPEN, CARLOS; MOTA, GUILHERME O.; PARENTE, ROBERTO F.; SATO, CRISTIANE M.. Counting Sparse k-edge-connected Hypergraphs with Given Number of Vertices and Edges. ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, v. 346, p. 10-pg., 2019-08-30. (18/04876-1)

LINTZMAYER, C. N.; MOTA, G. O.; SAMBINELLI, M.. Decomposing Split Graphs into Locally Irregular Graphs. ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, v. 346, p. 10-pg., 2019-08-30. (18/04876-1, 17/23623-4, 13/03447-6)

CERIOLI, MARCIA R.; FERNANDES, CRISTINA G.; LEE, ORLANDO; LINTZMAYER, CARLA N.; MOTA, GUILHERME O.; DA SILVA, CANDIDA N.. On Edge-magic Labelings of Forests. ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, v. 346, p. 9-pg., 2019-08-30. (18/04876-1, 15/11937-9, 13/03447-6)

COLLARES, MAURICIO; KOHAYAKAWA, YOSHIHARU; MOREIRA, CARLOS GUSTAVO; MOTA, GUILHERME OLIVEIRA; FERREIRA, CE; LEE, O; MIYAZAWA, FK. Constrained colourings of random graphs. PROCEEDINGS OF THE XI LATIN AND AMERICAN ALGORITHMS, GRAPHS AND OPTIMIZATION SYMPOSIUM, v. 195, p. 8-pg., 2021-01-01. (18/04876-1, 19/13364-7)

LINTZMAYER, C. N.; MOTA, G. O.; SAMBINELLI, M.. Decomposing split graphs into locally irregular graphs. DISCRETE APPLIED MATHEMATICS, v. 292, p. 33-44, MAR 31 2021. (17/23623-4, 18/04876-1, 13/03447-6)

KOHAYAKAWA, YOSHIHARU; MOTA, GUILHERME OLIVEIRA; PARCZYK, OLAF; SCHNITZER, JAKOB. The anti-Ramsey threshold of complete graphs. DISCRETE MATHEMATICS, v. 346, n. 5, p. 12-pg., 2023-02-01. (18/04876-1, 19/13364-7)