A análise de estruturas discretas de grandes proporções

• Processo: 07/56496-3
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Data de Início da vigência: 01 de março de 2008
• Data de Término da vigência: 28 de fevereiro de 2010
• Á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: Carlos Hoppen
• Instituição Sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Assunto(s): Combinatória Métodos assintóticos Teoria dos grafos Métodos probabilísticos
• Palavra(s)-Chave do Pesquisador: Combinatoria | Metodos Assintoticos | Metodos Probabilisticos | Teoria Dos Grafos

Resumo

Grafos e outras estruturas discretas de grandes dimensões são objeto de ativa pesquisa em combinatória, dadas as suas múltiplas aplicações às ciências naturais, sociais ou mesmo biomédicas. Porém, o estudo de tais estruturas por métodos diretos esbarram nas suas dimensões, pois tais objetos podem conter milhões ou mesmo bilhões de vértices. Concentramo-nos, portanto, em caminhos alternativos para a realização de tal objetivo. Em particular, apresentamos problemas nas áreas de grafos aleatórios, que tratam grafos como elementos de um espaço de probabilidade, técnica essa que tem obtido grande sucesso na obtenção de resultados sobre o comportamento assintótico de propriedades de grafos, bem como na área de testabilidade de propriedades e parâmetros, que tem contribuído com resultados de grande generalidade e elegância matemática. Além disso, mencionamos esforços no desenvolvimento de métodos heurísticos para analisar e gerar redes com determinadas propriedades e na análise matemática rigorosa de tais métodos. (AU)

Publicações científicas

(8)

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

HOPPEN, CARLOS; KOHAYAKAWA, YOSHIHARU; SAMPAIO, RUDINI M.. A note on permutation regularity. DISCRETE APPLIED MATHEMATICS, v. 160, n. 18, SI, p. 2716-2727, DEC 2012. (07/56496-3)

HOPPEN, CARLOS; KOHAYAKAWA, YOSHIHARU; LEFMANN, HANNO. Hypergraphs with many Kneser colorings. EUROPEAN JOURNAL OF COMBINATORICS, v. 33, n. 5, p. 28-pg., 2012-07-01. (07/56496-3)

HOPPEN, CARLOS; KOHAYAKAWA, YOSHIHARU; LEFMANN, HANNO. Hypergraphs with many Kneser colorings. EUROPEAN JOURNAL OF COMBINATORICS, v. 33, n. 5, SI, p. 816-843, JUL 2012. (07/56496-3)

HOPPEN, CARLOS; KOHAYAKAWA, YOSHIHARU; MOREIRA, CARLOS GUSTAVO; SAMPAIO, RUDINI MENEZES. Testing permutation properties through subpermutations. THEORETICAL COMPUTER SCIENCE, v. 412, n. 29, p. 3555-3567, JUL 1 2011. (07/56496-3)

BENJAMINI, ITAI; HOPPEN, CARLOS; OFEK, ERAN; PRATAT, PAWET; WORMALD, NICK. Geodesics and Almost Geodesic Cycles in Random Regular Graphs. JOURNAL OF GRAPH THEORY, v. 66, n. 2, p. 115-136, FEB 2011. (07/56496-3)

HOPPEN, CARLOS; KOHAYAKAWA, YOSHIHARU; MOREIRA, CARLOS GUSTAVO; RATH, BALAZS; SAMPAIOE, RUDINI MENEZES. Limits of permutation sequences. JOURNAL OF COMBINATORIAL THEORY SERIES B, v. 103, n. 1, p. 93-113, JAN 2013. (07/56496-3)

HOPPEN, CARLOS; KOHAYAKAWA, YOSHIHARU; SAMPAIO, RUDINI M.. A note on permutation regularity. DISCRETE APPLIED MATHEMATICS, v. 160, n. 18, p. 12-pg., 2012-12-01. (07/56496-3)

HOPPEN, CARLOS; KOHAYAKAWA, YOSHIHARU; MOREIRA, CARLOS GUSTAVO; SAMPAIO, RUDINI MENEZES; SIAM/ACM. Property testing and parameter testing for permutations. PROCEEDINGS OF THE TWENTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, v. 135, p. 2-pg., 2010-01-01. (07/56496-3, 03/09925-5)