Date of Award
Spring 2020
Document Type
Open Access Dissertation
Department
Mathematics
First Advisor
Linyuan Lu
Abstract
This thesis studies some problems in extremal and probabilistic combinatorics, Ricci curvature of graphs, spectral hypergraph theory and the interplay between these areas. The first main focus of this thesis is to investigate several Ramseytype problems on graphs, hypergraphs and sequences using probabilistic, combinatorial, algorithmic and spectral techniques:
 The sizeRamsey number Rˆ(G, r) is defined as the minimum number of edges in a hypergraph H such that every redgecoloring of H contains a monochromatic copy of G in H. We improved a result of Dudek, La Fleur, Mubayi and Rödl [ J. Graph Theory 2017 ] on the sizeRamsey number of tight paths and extended it to more colors.

An edgecolored graph G is called rainbow if every edge of G receives a different color. The antiRamsey number of t edgedisjoint rainbow spanning trees, denoted by r(n, t), is defined as the maximum number of colors in an edgecoloring of Kn containing no t edgedisjoint rainbow spanning trees. Confirming a conjecture of Jahanbekam and West [J. Graph Theory 2016], we determine the antiRamsey number of t edgedisjoint rainbow spanning trees for all values of n and t.

We study the extremal problems on Berge hypergraphs. Given a graph G = (V, E), a hypergraph H is called a BergeG, denoted by BG, if there exists an injection i ∶ V (G) → V (H) and a bijection f ∶ E(G) → E(H) such that for every e = uv ∈ E(G), (i(u), i(v)) ⊆ f(e). We investigate the hypergraph Ramsey number of Berge cliques, the coverRamsey number of Berge hypergraphs, the coverTurán desity of Berge hypergraphs as well as Hamiltonian Berge cycles in 3uniform hypergraphs.
The second part of the thesis uses the ‘geometry’ of graphs to derive concentration inequalities in probabilities spaces. We prove an AzumaHoeffdingtype inequality in several classical models of random configurations, including the ErdősRényi random graph models G(n, p) and G(n,M), the random dout(in)regular directed graphs, and the space of random permutations. The main idea is using Ollivier’s work on the Ricci curvature of Markov chairs on metric spaces. We give a cleaner form of such concentration inequality in graphs. Namely, we show that for any Lipschitz function f on any graph (equipped with an ergodic random walk and thus an invariant distribution ν) with Ricci curvature at least κ > 0, we have
ν (∣f − Eνf∣ ≥ t) ≤ 2 exp (t ^{2}κ/7).
The third part of this thesis studies a problem in spectral hypergraph theory, which is the interplay between graph theory and linear algebra. In particular, we study the maximum spectral radius of outerplanar 3uniform hypergraphs. Given a hypergraph H, the shadow of H is a graph G with V (G) = V (H) and E(G) = {uv ∶ uv ∈ h for some h ∈ E(H)}. A 3uniform hypergraph H is called outerplanar if its shadow is outerplanar and all faces except the outer face are triangles, and the edge set of H is the set of triangle faces of its shadow. We show that the outerplanar 3uniform hypergraph on n vertices of maximum spectral radius is the unique hypergraph with shadow K_{1} + P_{n−1}.
Recommended Citation
Wang, Z.(2020). Connections Between Extremal Combinatorics, Probabilistic Methods, Ricci Curvature of Graphs, and Linear Algebra. (Doctoral dissertation). Retrieved from https://scholarcommons.sc.edu/etd/5771