Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 34 for “"Ramsey Theory"”.
-
Ramsey Theory
<p>The Ramsey number $R(r, b)$ is the least positive integer such that every edge 2-coloring of the complete graph $K_{R(r, b)}$ with colors red and blue either embeds a red $K_r$ or a blue $K_b$. We explore various methods to find lower bounds on $R(r,b)$, finding new results on fibrations and …
-
An exploration in Ramsey theory
1 PDF file (viii, 39 pages)
-
Ramsey Theory Using Matroid Minors
This thesis considers a Ramsey Theory question for graphs and regular matroids. Specifically, how many elements N are required in a 3-connected graphic or regular matroid to force the existence of certain specified minors in that matroid? This question cannot be answered for an arbitrary collection …
-
Ramsey theory and its application
… this dissertation, we study three problems about Ramsey theory. First, we prove a self-dual Ramsey theorem for parameter systems which is a generalization of the self-dual Ramsey theorem developed by Solecki. Second, we prove a Ramsey theorem for finite sets equipped with a partial order and a …
-
Some problems in Graph Ramsey Theory
A graph G is r-Ramsey minimal with respect to a graph H if every r-coloring of the edges of G yields a monochromatic copy of H, but the same is not true for any proper subgraph of G. The study of the properties of graphs that are Ramsey minimal with respect to some H and similar problems is known …
-
Unprovability and phase transitions in Ramsey theory
… It is a strengthened form of the finite Ramsey theorem which can not be proved, nor refuted in Peano Arithmetic. In this dissertation we investigate several other unprovable statements of Ramseyan nature and determine the threshold functions for the related phase transitions. Chapter 1 …
-
An Introduction to Ramsey Theory on Graphs
… is written as a single source introduction to Ramsey Theory for advanced undergraduates and graduate students.
-
Results in Ramsey theory and extremal graph theory
… relating to graphs. The first problem is in Ramsey theory, while the others are in extremal graph theory. In Chapter 2, which is joint work with Vojtěch Dvořák, we consider the Ramsey number $R(F_n)$ of the fan graph $F_n$, a graph consisting of $n$ triangles which all share a common vertex. …
-
Extremal problems in combinatorial geometry and Ramsey theory
… to specific problems in combinatorial geometry, Ramsey theory and graph theory. We first study extremal questions in geometric graph theory, that is, the existence of collections of edges with a specified crossing pattern in drawings of graphs in the plane with sufficiently many edges. Among …
-
Problems in Ramsey theory, probabilistic combinatorics and extremal graph theory
… this dissertation, we treat several problems in Ramsey theory, probabilistic combinatorics and extremal graph theory.
-
Results in Extremal Graph Theory, Ramsey Theory and Additive Combinatorics
… we consider a central problem in Extremal Graph Theory. The extremal number (or Turán number) ex(n,H) of a graph H is the maximum number of edges in an H-free graph on n vertices. It is a major area of research to better understand the extremal number of bipartite graphs. In this chapter we …
-
Ramsey theory: The Erdős-Gyárfás problem and ordered size Ramsey questions
DSpace SAF Submission Ingestion Package generated from Vireo submission #16387 on 2021-09-16 at 16:42:26
-
Degree Ramsey theory, game and Roman domination, and game saturation in graphs
"We examine several problems in extremal graph theory, emphasizing problems involving games on graphs. In Chapter 2, we study a variant of Ramsey theory, seeking Ramsey hosts with small maximum degree. We focus on finding such hosts for trees and cycles. In Chapter 3 we consider the ""on-line"" …
-
Ramsey regions and simplicial homology tables for graphs
Ramsey Theory is the investigation of edge-colored graphs which force a monochromatic subgraph. We devise a way of breaking certain Ramsey Theory problems into "smaller" pieces so that information about Ramsey Theory can be gained without solving the entire problem, (which is often difficult to …
-
Topological Dynamics of Automorphism Groups of omega-homogeneous Structures via Near Ultrafilters
… of automorphisms of structures and structural Ramsey theory from countable to uncountable structures. This allows us to provide new examples of explicit descriptions of universal minimal flows as well as of extremely amenable groups. We identify new classes of finite structures satisfying the …
-
Extremal problems on edge-colorings, independent sets, and cycle spectra of graphs
We study problems in extremal graph theory with respect to edge-colorings, independent sets, and cycle spectra. In Chapters 2 and 3, we present results in Ramsey theory, where we seek Ramsey host graphs with small maximum degree. In Chapter 4, we study a Ramsey-type problem on edge-labeled trees, …
-
Poset saturation and other combinatorial results
… fall into four broad areas: poset saturation, Ramsey theory, pursuit and evasion, and union-closed families. Chapter 2 is dedicated to the area of poset saturation. Given a finite poset P, we call a family F of subsets of [n] P-saturated if F does not contain an induced copy of P, but adding …
-
Algorithms and Algorithmic Barriers in High-Dimensional Statistics and Random Combinatorial Structures
… statistical physics and in particular spin glass theory. We establish that both models exhibit the Overlap Gap Property (OGP), an intricate geometrical property that is known to be a rigorous barrier for large classes of algorithms. We then leverage the OGP to rule out certain important classes of …
-
Topological Ramsey Spaces, Associated Ultrafilters, and Their Applications to the Tukey Theory of Ultrafilters and Dedekind Cuts of Nonstandard Arithmetic
… contributions to the areas of combinatorial set theory, the model theory of arithmetic, and the Tukey theory of ultrafilters. The main results are broken into three parts.</p> <p>In the first part, we identify some new partition relations among finite trees and use them to answer an open question …
-
Cliques in graphs
… degree~$\delta$. A fundamental result in Graph Theory states that a triangle-free graph of order $n$ has at most $n^2/4$ edges. Hence, a triangle-free graph has minimum degree at most $n/2$, so if $k_3(n,\delta) =0$ then $\delta \le n/2$. For $n/2 \leq \delta \leq 4n/5$, I have evaluated …
Page 1 of 2