東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Randomly Perturbed Multipartite Graphs /

Gomez-Leos, Enrique,

Linked to FindBook

Google Book

Amazon

博客來

Randomly Perturbed Multipartite Graphs /

Record Type:	Electronic resources : Monograph/item
Title/Author:	Randomly Perturbed Multipartite Graphs // Enrique Gomez-Leos.
Author:	Gomez-Leos, Enrique,
Description:	1 electronic resource (86 pages)
Notes:	Source: Dissertations Abstracts International, Volume: 86-12, Section: A.
Contained By:	Dissertations Abstracts International86-12A.
Subject:	Mathematics. -
Online resource:	https://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=31938306
ISBN:	9798286430147

Randomly Perturbed Multipartite Graphs /
Gomez-Leos, Enrique,

Randomly Perturbed Multipartite Graphs /Enrique Gomez-Leos. - 1 electronic resource (86 pages)

Source: Dissertations Abstracts International, Volume: 86-12, Section: A.

In this thesis, we solve two tiling problems in the area of randomly perturbed graph theory. Tiling problems form a central part of both extremal and random graph theory. Many results in extremal graph theory concern minimum degree conditions that guarantee the existence of some spanning subgraph. The spanning subgraphs we will be concerned with are perfect tilings. Given a graph G and a subgraph H we will call any collection of vertex-disjoint copies of H in G, an H-tiling of G. Furthermore, we will say that an n vertex graph G has a perfect H-tiling if G has a subgraph consisting of n/|H| vertex-disjoint copies of H.A typical graph tiling problem asks the following: Given a graph G on n vertices and a graph H, what is the minimum degree condition that guarantees the existence of a perfect H-tiling. If H = K3, a celebrated result of Corradi and Hajnal gives the minimum degree of finding a perfect K3-tiling. Hajnal and Szemeredi generalized this result to cliques of arbitrary size. The problem has also been studied in the setting in which G is bipartite, tripartite, quadrapartite, and multipartite.In the setting of random graph theory, a question of interest is to determine the probability threshold for the appearance of an H-tiling in the Erdos-Renyi random graph, G(n, p). Johansson, Kahn, and Vu determined the threshold for all strictly balanced graphs, and Gerke and McDowell resolved the remaining cases and provided generalizations to the random multipartite graph, Gr(n, p).Bohman, Frieze, and Martin introduced the randomly perturbed graph which connects the two questions together. In this model one begins with a graph G on n vertices with minimum degree δ(G) ≥ αn, for some α ∈ (0, 1), and adds random edges, each with probability p = p(n) from the set of non-edges of G. The natural question is to determine the probability threshold p (i.e. how many edges) must be added so that the resulting graph contains a perfect H-tiling with high probability. Balogh, Treglown, and Wagner determined the probability threshold for the appearance of a perfect H-tiling in a graph on n vertices with minimum degree at least αn for any graph H.Inspired by the multipartite analog of Hajnal-Szemeredi due to Keevash and Mycroft and Balogh, Treglown, and Wagner, we prove bipartite and multipartite analogs of [1]. In doing so, we initiate the study of the randomly perturbed multipartite graph. We define the randomly perturbed multipartite graph to be the union of a balanced r-partite graph on rn vertices, with the Erdos-Renyi random r-partite graph, Gr(n, p). In Chapter 1, we provide a general introduction. In Chapter 2, we determine the probability threshold for which the randomly perturbed bipartite graph contains a perfect Kh,h tiling for any h ≥ 1. In Chapter 3, we determine the probability threshold for which the randomly perturbed r-partite graph contains a perfect Kr-tiling for all r ≥ 3.

English

ISBN: 9798286430147Subjects--Topical Terms:

515831
Mathematics.
Subjects--Index Terms:

Combinatorics

Randomly Perturbed Multipartite Graphs /
LDR:04282nmm a22004093i 4500 001 2433442
005 20250825062333.5
006 m o d
007 cr|nu||||||||
008 261011s2025 miu||||||m |||||||eng d
020 $a 9798286430147
035 $a (MiAaPQD)AAI31938306
035 $a AAI31938306
040 $a MiAaPQD $b eng $c MiAaPQD $e rda
100 1 $a Gomez-Leos, Enrique, $e author. $0 (orcid)0000-0002-0064-0193 $3 3823056
245 1 0 $a Randomly Perturbed Multipartite Graphs / $c Enrique Gomez-Leos.
264 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2025
300 $a 1 electronic resource (86 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertations Abstracts International, Volume: 86-12, Section: A.
500 $a Advisors: Martin, Ryan R. Committee members: Zerbib, Shira; Iverson, Joseph; Wu, Ruoyu; Lidicky, Bernard.
502 $b Ph.D. $c Iowa State University $d 2025.
520 $a In this thesis, we solve two tiling problems in the area of randomly perturbed graph theory. Tiling problems form a central part of both extremal and random graph theory. Many results in extremal graph theory concern minimum degree conditions that guarantee the existence of some spanning subgraph. The spanning subgraphs we will be concerned with are perfect tilings. Given a graph G and a subgraph H we will call any collection of vertex-disjoint copies of H in G, an H-tiling of G. Furthermore, we will say that an n vertex graph G has a perfect H-tiling if G has a subgraph consisting of n/|H| vertex-disjoint copies of H.A typical graph tiling problem asks the following: Given a graph G on n vertices and a graph H, what is the minimum degree condition that guarantees the existence of a perfect H-tiling. If H = K3, a celebrated result of Corradi and Hajnal gives the minimum degree of finding a perfect K3-tiling. Hajnal and Szemeredi generalized this result to cliques of arbitrary size. The problem has also been studied in the setting in which G is bipartite, tripartite, quadrapartite, and multipartite.In the setting of random graph theory, a question of interest is to determine the probability threshold for the appearance of an H-tiling in the Erdos-Renyi random graph, G(n, p). Johansson, Kahn, and Vu determined the threshold for all strictly balanced graphs, and Gerke and McDowell resolved the remaining cases and provided generalizations to the random multipartite graph, Gr(n, p).Bohman, Frieze, and Martin introduced the randomly perturbed graph which connects the two questions together. In this model one begins with a graph G on n vertices with minimum degree δ(G) ≥ αn, for some α ∈ (0, 1), and adds random edges, each with probability p = p(n) from the set of non-edges of G. The natural question is to determine the probability threshold p (i.e. how many edges) must be added so that the resulting graph contains a perfect H-tiling with high probability. Balogh, Treglown, and Wagner determined the probability threshold for the appearance of a perfect H-tiling in a graph on n vertices with minimum degree at least αn for any graph H.Inspired by the multipartite analog of Hajnal-Szemeredi due to Keevash and Mycroft and Balogh, Treglown, and Wagner, we prove bipartite and multipartite analogs of [1]. In doing so, we initiate the study of the randomly perturbed multipartite graph. We define the randomly perturbed multipartite graph to be the union of a balanced r-partite graph on rn vertices, with the Erdos-Renyi random r-partite graph, Gr(n, p). In Chapter 1, we provide a general introduction. In Chapter 2, we determine the probability threshold for which the randomly perturbed bipartite graph contains a perfect Kh,h tiling for any h ≥ 1. In Chapter 3, we determine the probability threshold for which the randomly perturbed r-partite graph contains a perfect Kr-tiling for all r ≥ 3.
546 $a English
590 $a School code: 0097
650 4 $a Mathematics. $3 515831
650 4 $a Theoretical mathematics. $3 3173530
650 4 $a Mathematics education. $3 641129
653 $a Combinatorics
653 $a Graph theory
653 $a Quadrapartite
690 $a 0405
690 $a 0642
690 $a 0280
710 2 $a Iowa State University. $b Mathematics. $e degree granting institution. $3 3822982
720 1 $a Martin, Ryan R. $e degree supervisor.
773 0 $t Dissertations Abstracts International $g 86-12A.
790 $a 0097
791 $a Ph.D.
792 $a 2025
856 4 0 $u https://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=31938306