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 60 for “"Extremal Combinatorics"”.
-
Problems in extremal combinatorics
In this thesis, we prove results in extremal combinatorics. The thesis is divided into three parts. In the first part, for fixed integers $n \ge k \ge 2$ and $s \ge 2$, we study the chromatic number of the subgraphs of the Kneser graph $\textrm{KG}(n,k)$ induced by the family the $s$-stable sets in …
-
Problems in extremal combinatorics
We consider a variety of problems in extremal graph and set theory. Given a property $\Gamma$ and a family of sets ${\mathcal F}$, let $f({\mathcal F},\Gamma)$ be the size of the largest subfamily of ${\mathcal F}$ having property $\Gamma$. Let $f(m,\Gamma)$ be the minimum of $f({\mathcal …
-
New results in extremal combinatorics
Extremal problems, in general, ask for the optimal size of certain finite objects when some restrictions are imposed. In extremal combinatorics, a major field in combinatorics, one studies how global properties guarantee the existence of local substructures, or equivalently, how avoiding local …
-
Spectral Methods in Extremal Combinatorics
Extremal combinatorics studies how large a collection of objects can be if it satisfies a given set of restrictions. Inspired by a classical theorem due to Erdos, Ko and Rado, Simonovits and Sos posed the following problem: determine how large a collection of graphs on the vertex set {1,...,n} can …
-
On problems in Extremal Combinatorics
Extremal Combinatorics studies how large or how small a structure can be, if it does not contain certain forbidden configuration. One of its major areas of study is extremal set theory, where the structures considered are families of sets, and the forbidden configurations are restricted …
-
Some Results in Extremal Combinatorics
Extremal Combinatorics is one of the central and heavily contributed areas in discrete mathematics, and has seen an outstanding growth during the last few decades. In general, it deals with problems regarding determination and/or estimation of the maximum or the minimum size of a combinatorial …
-
Extremal combinatorics, graph limits and computational complexity
… thesis is primarily focused on problems in extremal combinatorics, although we will also consider some questions of analytic and algorithmic nature. </p> <p>The <em>d-dimensional hypercube</em> is the graph with vertex set {0,1}<sup><em>d</em></sup> where two vertices are adjacent if they …
-
Problems in Positional Games and Extremal Combinatorics
… thesis deals with two different directions of extremal graph theory. In the first part we consider two kinds of positional games, the so-called strong games and the Maker-Breaker games. In the second chapter we consider the following strong Ramsey game: Two players take turns in claiming a …
-
Local approaches to global problems in extremal combinatorics
In this thesis we consider five problems in extremal combinatorics all of which which are all amenable to approaches based on local structure. The first part of this thesis looks at rainbow subgraphs at extremal thresholds. We show that as soon as they appear, we can also find rainbow copies of …
-
Connections Between Extremal Combinatorics, Probabilistic Methods, Ricci Curvature of Graphs, and Linear Algebra
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 …
-
Explorations in Extremal Combinatorics: Graph Spectra, Codegree Squared Sum of Hypergraphs and Lin-Lu-Yau Ricci Curvature
This dissertation explores a variety of extremal problems in spectral graph theory, hypergraph Tur\'an theory in the $\ell_2$-norm, and Lin-Lu-Yau Ricci curvature. We begin by studying the maximization of linear combinations of eigenvalues in relation to the adjacency matrix of a graph. For a graph …
-
Distality to and from combinatorics
… notion of distality and concepts from combinatorics: developments in distality both lead to and come from those in combinatorics. Chapter 3 demonstrates the from direction. We prove that expansions of Presburger arithmetic by a predicate R ⊆ ℕ are distal when R satisfies certain …
-
Towards a general theory of Erdős-Ko-Rado combinatorics
… larger than n-1/k-1. This fundamental result of extremal combinatorics is now known as the EKR theorem for intersecting set families. Since then, there has been a proliferation of similar EKR theorems in extremal combinatorics that characterize families of more sophisticated objects that are …
-
New Analytical Methods for Online Binary Search Trees
… of binary search trees: potential functions and extremal combinatorics. In the first part, we focus on the potential function method, which is widely used but mysterious in how it works. We introduce new charging schemes based on inversion counting, a popular potential function for list updates …
-
Two problems in extremal set theory
… focus of this dissertation is on two problems in extremal set theory, which is a branch of extremal combinatorics. The general problem in extremal set theory is to start with all collections of subsets of an underlying ground set, apply restrictions, and then ask how large or small some property …
-
Quasirandom forcing in regular tournaments
… structures has been a well-known problem in Extremal Combinatorics since 1987. In this work, we study quasirandom forcing in the case of tournaments. We say that a tournament H forces quasirandomness if in every quasirandom sequence (T_n)_{n\in \mathbb{N}} of tournaments of increasing order, …
-
Classification of Tripartite Tensors with Small Geometric Ranks
… tool to study algebraic complexity theory, extremal combinatorics and quantum information theory. This dissertation studies the classification of tripartite tensors with small geometric ranks. We introduce primitive tensors and compression tensors, which reduces the classification problem to …
-
SOME EXTREMAL PROBLEMS UNDER GROWTH/EXPANSION CONSTRAINTS
Extremal combinatorics is the study of extremal properties of combinatorial objects under certain constraints. This thesis explores several extremal problems under growth and expansion constraints. The content beyond the Introduction (Chapter 1) is divided into three chapters, each associated with …
-
Forbidden substructures: induced subgraphs, Ramsey games, and sparse hypergraphs
We study problems in extremal combinatorics with respect to forbidden induced subgraphs, forbidden colored subgraphs, and forbidden subgraphs. In Chapter 2, we determine exactly which graphs H have the property that almost every H-free graph has a vertex partition into k cliques and independent …
Page 1 of 3