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 the number of orientations of random graphs with no directed cycles of a given length

Texto completo
Autor(es):
Allen, P. [1] ; Kohayakawa, Y. [2] ; Mota, G. O. [2] ; Parente, R. F. [2]
Número total de Autores: 4
Afiliação do(s) autor(es):
[1] London Sch Econ, Dept Math, London WC2A 2AE - England
[2] Univ Sao Paulo, Inst Matemat & Estat, BR-05508090 Sao Paulo - Brazil
Número total de Afiliações: 2
Tipo de documento: Artigo Científico
Fonte: ELECTRONIC JOURNAL OF COMBINATORICS; v. 21, n. 1 MAR 10 2014.
Citações Web of Science: 0
Resumo

Let (H) over right arrow be an orientation of a graph H. Alon and Yuster proposed the problem of determining or estimating D(n, m, (H) over right arrow), the maximum number of (H) over right arrow -free orientations a graph with n vertices and m edges may have. We consider the maximum number of (H) over right arrow -free orientations of typical graphs G(n, m) with n vertices and m edges. Suppose (H) over right arrow = C-l(((sic))) is the directed cycle of length l >= 3. We show that if m >> n(1+1/(l-1)), then this maximum is 2(o(m)), while m << n(1+1/(l-1)), the it is 2((1-o(1))m). (AU)

Processo FAPESP: 13/07699-0 - Centro de Pesquisa, Inovação e Difusão em Neuromatemática - NeuroMat
Beneficiário:Oswaldo Baffa Filho
Modalidade de apoio: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs
Processo FAPESP: 10/09555-7 - Problemas estruturais, probabilísticos e de imersão em teoria extremal dos grafos
Beneficiário:Peter David Allen
Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
Processo FAPESP: 12/00036-2 - Combinatória assintótica de estruturas esparsas e regularidade
Beneficiário:Guilherme Oliveira Mota
Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Doutorado
Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
Beneficiário:Carlos Eduardo Ferreira
Modalidade de apoio: Auxílio à Pesquisa - Temático
Processo FAPESP: 13/20733-2 - Combinatória extremal e probabilística
Beneficiário:Guilherme Oliveira Mota
Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Pós-Doutorado
Processo FAPESP: 09/06294-0 - Combinatória assintótica de estruturas esparsas e regularidade
Beneficiário:Guilherme Oliveira Mota
Modalidade de apoio: Bolsas no Brasil - Doutorado