Two problems in modern combinatorics

Author(s)

Guilherme Oliveira Mota

• Document type: Doctoral Thesis
• Press: São Paulo.
• Institution: Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI)
• Defense date: 2013-08-30

Examining board members

Yoshiharu Kohayakawa; Fabricio Siqueira Benevides; Carlos Hoppen; Daniel Morgato Martin; Rudini Menezes Sampaio

• Advisor: Yoshiharu Kohayakawa

Abstract

Two combinatorial problems are studied: (i) determining the number of copies of a fixed hipergraph in uniform pseudorandom hypergraphs, and (ii) estimating the two and three color Ramsey numbers for graphs with small bandwidth and bounded maximum degree. We give a counting lemma for the number of copies of linear k-uniform \\emph hypergraphs (connector is a generalization of triangle for hypergraphs) that are contained in some sparse hypergraphs G. Let H be a linear k-uniform connector-free hypergraph and let G be a k-uniform hypergraph with n vertices. Set d_H=\\max\\{\\delta(J)\\colon J\\subset H\\} and D_H=\\min\\{kd_H,\\Delta(H)\\}. We proved that if the vertices of G do not have large degree, small families of (k-1)-element sets of V(G) do not have large common neighbourhood and most of the pairs of sets in {V(G)\\choose k-1} have the `right\' number of common neighbours, then the number of embeddings of H in G is (1+o(1))n^{|V(H)|}p^{|E(H)|}, given that p\\gg n^{1/D_H} and |E(G)|={n\\choose k}p. This generalizes a result by Kohayakawa, R\\\"odl and Sissokho [Embedding graphs with bounded degree in sparse pseudo\\-random graphs, Israel J. Math. 139 (2004), 93--137], who proved that, for p as above, this result holds for graphs, where H is a triangle-free graph. We determine asymptotically the two and three Ramsey numbers for bipartite graphs with small bandwidth and bounded maximum degree. More generally, we determine asymptotically the two color Ramsey number for bipartite graphs with small bandwidth and bounded maximum degree and the three color Ramsey number for such graphs with the additional assumption that both classes of the bipartite graph have almost the same size. (AU)

• FAPESP's process: 09/06294-0 - Asymptotic combinatorics of sparse structures and regularity
• Grantee: Guilherme Oliveira Mota
• Support Opportunities: Scholarships in Brazil - Doctorate