Asymptotic combinatorics of sparse structures and regularity

• Grant number: 09/06294-0
• Support Opportunities: Scholarships in Brazil - Doctorate
• Start date: July 01, 2009
• End date: July 31, 2013
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computational Mathematics
• Principal Investigator: Yoshiharu Kohayakawa
• Grantee: Guilherme Oliveira Mota
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
• Associated scholarship(s): 12/00036-2 - Asymptotic combinatorics of sparse structures and regularity, BE.EP.DR

Abstract

This is the research proposal for the doctoral work of Guilherme Oliveira Mota, who will be supervised by Y. Kohayakawa, at the Instituto de Matemática e Estatística, Universidade de São Paulo, from July 2009 to December 2012 (including a six-month stay abroad). This proposal focuses on the asymptotic study of sparse combinatorial structures. This investigation will be based on Szemerédi's regularity lemma and its several variants. This lemma is essential in the study of convergent sequences of dense graph. Mota will investigate, among others, convergent sequences of sparse graphs, using as a tool appropriate variants of the regularity lemma. We believe that this project will be successfully concluded within the estimated time, as Mota has an excellent background, from his undergraduate and Master's courses. This proposal has as its starting point a body of sophisticated results due to Bollobás, Borgs, Chayes, Elek, Lovász, Riordan, Rödl, Schacht, Szegedy, Vesztergombi, among others, and some of the work of the supervisor involving the regularity lemma for sparse graphs. To complete this project successfully, Mota will have to acquire solid expertise in combinatorics and will have to make substantial scientific contributions to the area.

Scientific publications

(6)

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

KOHAYAKAWA, Y.; KONSTADINIDIS, P. B.; MOTA, G. O.. On an anti-Ramsey threshold for sparse graphs with one triangle. JOURNAL OF GRAPH THEORY, v. 87, n. 2, p. 176-187, FEB 2018. (09/06294-0, 13/07699-0, 13/20733-2, 13/03447-6, 13/11431-2)

KOHAYAKAWA, YOSHIHARU; MOTA, GUILHERME OLIVEIRA; SCHACHT, MATHIAS; TARAZ, ANUSCH. Counting results for sparse pseudorandom hypergraphs I. EUROPEAN JOURNAL OF COMBINATORICS, v. 65, p. 276-287, OCT 2017. (09/06294-0, 13/07699-0, 13/20733-2, 13/03447-6, 13/11431-2)

MOTA, G. O.; SARKOEZY, G. N.; SCHACHT, M.; TARAZ, A.. Ramsey numbers for bipartite graphs with small bandwidth. EUROPEAN JOURNAL OF COMBINATORICS, v. 48, n. SI, p. 165-176, AUG 2015. (09/06294-0, 12/00036-2)

KOHAYAKAWA, Y.; KONSTADINIDIS, P. B.; MOTA, G. O.. On an anti-Ramsey threshold for random graphs. EUROPEAN JOURNAL OF COMBINATORICS, v. 40, p. 26-41, AUG 2014. (13/03447-6, 13/07699-0, 09/06294-0, 12/00036-2)

ALLEN, P.; KOHAYAKAWA, Y.; MOTA, G. O.; PARENTE, R. F.. On the number of orientations of random graphs with no directed cycles of a given length. ELECTRONIC JOURNAL OF COMBINATORICS, v. 21, n. 1, MAR 10 2014. (13/07699-0, 10/09555-7, 12/00036-2, 13/03447-6, 13/20733-2, 09/06294-0)

MOTA, G. O.; SARKOEZY, G. N.; SCHACHT, M.; TARAZ, A.. Ramsey numbers for bipartite graphs with small bandwidth. EUROPEAN JOURNAL OF COMBINATORICS, v. 48, p. 12-pg., 2015-08-01. (09/06294-0, 12/00036-2)

Academic Publications

(References retrieved automatically from State of São Paulo Research Institutions)

MOTA, Guilherme Oliveira. Two problems in modern combinatorics. 2013. Doctoral Thesis - Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI) São Paulo.