東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Connections Between Extremal Combina...

Wang, Zhiyu.

Linked to FindBook

Google Book

Amazon

博客來

Connections Between Extremal Combinatorics, Probabilistic Methods, Ricci Curvature of Graphs, and Linear Algebra.

Record Type:	Electronic resources : Monograph/item
Title/Author:	Connections Between Extremal Combinatorics, Probabilistic Methods, Ricci Curvature of Graphs, and Linear Algebra./
Author:	Wang, Zhiyu.
Published:	Ann Arbor : ProQuest Dissertations & Theses, : 2020,
Description:	184 p.
Notes:	Source: Dissertations Abstracts International, Volume: 82-02, Section: B.
Contained By:	Dissertations Abstracts International82-02B.
Subject:	Mathematics. -
Online resource:	https://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=27835458
ISBN:	9798662433656

Connections Between Extremal Combinatorics, Probabilistic Methods, Ricci Curvature of Graphs, and Linear Algebra.
Wang, Zhiyu.

Connections Between Extremal Combinatorics, Probabilistic Methods, Ricci Curvature of Graphs, and Linear Algebra. - Ann Arbor : ProQuest Dissertations & Theses, 2020 - 184 p.

Source: Dissertations Abstracts International, Volume: 82-02, Section: B.

Thesis (Ph.D.)--University of South Carolina, 2020.

This item must not be sold to any third party vendors.

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 Ramsey-type problems on graphs, hypergraphs and sequences using probabilistic, combinatorial, algorithmic and spectral techniques:The size-Ramsey number R(G, r) is defined as the minimum number of edges in a hypergraph H such that every r-edge-coloring of H contains a monochromatic copy of G in H. We improved a result of Dudek, La Fleur, Mubayi and Rodl [ J. Graph Theory 2017 ] on the size-Ramsey number of tight paths and extended it to more colors.An edge-colored graph G is called rainbow if every edge of G receives a different color. The anti-Ramsey number of t edge-disjoint rainbow spanning trees, denoted by r(n, t), is defined as the maximum number of colors in an edge-coloring of Kn containing no t edge-disjoint rainbow spanning trees. Confirming a conjecture of Jahanbekam and West [J. Graph Theory 2016], we determine the anti-Ramsey number of t edge-disjoint 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 Berge-G, 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 cover-Ramsey number of Berge hypergraphs, the cover-Turan desity of Berge hypergraphs as well as Hamiltonian Berge cycles in 3-uniform hypergraphs.The second part of the thesis uses the 'geometry' of graphs to derive concentration inequalities in probabilities spaces. We prove an Azuma-Hoeffding-type inequality in several classical models of random configurations, including the Erdos-Renyi random graph models G(n, p) and G(n,M), the random d-out(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 (− (t2κ )/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 3-uniform 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 3-uniform 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 3-uniform hypergraph on n vertices of maximum spectral radius is the unique hypergraph with shadow K1 + Pn−1.

ISBN: 9798662433656Subjects--Topical Terms:

515831
Mathematics.
Subjects--Index Terms:

Extremal combinatorics

Connections Between Extremal Combinatorics, Probabilistic Methods, Ricci Curvature of Graphs, and Linear Algebra.
LDR:04330nmm a2200373 4500 001 2284807
005 20211124093227.5
008 220723s2020 ||||||||||||||||| ||eng d
020 $a 9798662433656
035 $a (MiAaPQ)AAI27835458
035 $a AAI27835458
040 $a MiAaPQ $c MiAaPQ
100 1 $a Wang, Zhiyu. $3 3564005
245 1 0 $a Connections Between Extremal Combinatorics, Probabilistic Methods, Ricci Curvature of Graphs, and Linear Algebra.
260 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2020
300 $a 184 p.
500 $a Source: Dissertations Abstracts International, Volume: 82-02, Section: B.
500 $a Advisor: Lu, Linyuan.
502 $a Thesis (Ph.D.)--University of South Carolina, 2020.
506 $a This item must not be sold to any third party vendors.
520 $a 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 Ramsey-type problems on graphs, hypergraphs and sequences using probabilistic, combinatorial, algorithmic and spectral techniques:The size-Ramsey number R(G, r) is defined as the minimum number of edges in a hypergraph H such that every r-edge-coloring of H contains a monochromatic copy of G in H. We improved a result of Dudek, La Fleur, Mubayi and Rodl [ J. Graph Theory 2017 ] on the size-Ramsey number of tight paths and extended it to more colors.An edge-colored graph G is called rainbow if every edge of G receives a different color. The anti-Ramsey number of t edge-disjoint rainbow spanning trees, denoted by r(n, t), is defined as the maximum number of colors in an edge-coloring of Kn containing no t edge-disjoint rainbow spanning trees. Confirming a conjecture of Jahanbekam and West [J. Graph Theory 2016], we determine the anti-Ramsey number of t edge-disjoint 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 Berge-G, 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 cover-Ramsey number of Berge hypergraphs, the cover-Turan desity of Berge hypergraphs as well as Hamiltonian Berge cycles in 3-uniform hypergraphs.The second part of the thesis uses the 'geometry' of graphs to derive concentration inequalities in probabilities spaces. We prove an Azuma-Hoeffding-type inequality in several classical models of random configurations, including the Erdos-Renyi random graph models G(n, p) and G(n,M), the random d-out(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 (− (t2κ )/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 3-uniform 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 3-uniform 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 3-uniform hypergraph on n vertices of maximum spectral radius is the unique hypergraph with shadow K1 + Pn−1.
590 $a School code: 0202.
650 4 $a Mathematics. $3 515831
650 4 $a Theoretical mathematics. $3 3173530
650 4 $a Statistics. $3 517247
653 $a Extremal combinatorics
653 $a Graph theory
653 $a Probabilistic methods
653 $a Ricci curvature
653 $a Spectral hypergraph theory
690 $a 0405
690 $a 0642
690 $a 0463
710 2 $a University of South Carolina. $b Mathematics. $3 1679331
773 0 $t Dissertations Abstracts International $g 82-02B.
790 $a 0202
791 $a Ph.D.
792 $a 2020
793 $a English
856 4 0 $u https://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=27835458