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 24 for “"Probabilistic Combinatorics"”.
-
Topics In Probabilistic Combinatorics
This paper is a compilation of results in combinatorics utilizing the probabilistic method. Below is a brief description of the results highlighted in each chapter. Chapter 1 provides basic definitions, lemmas, and theorems from graph theory, asymptotic analysis, and probability which will be used …
-
Problems in extremal and probabilistic combinatorics
… thesis we consider some problems in extremal and probabilistic combinatorics.</p> <p>In Chapter 2 we determine the maximum number of induced cycles that can be contained in a graph on <em>n</em> ≥ <em>n</em><sub>0</sub> vertices, and show that there is a unique graph that achieves this maximum. …
-
Problems in Extremal and Probabilistic Combinatorics
… presents advances in two central areas of modern combinatorics: Extremal Hypergraph Theory and Random Graph Theory. The results are presented in three parts. First, we resolve a longstanding open problem in the theory of random graphs known as the Kim-Vu Sandwich Conjecture (2004). This conjecture …
-
A statistical physics approach to probabilistic combinatorics
… that links together statistical physics and combinatorics is the phenomenon of phase transition. Broadly interpreted, this refers to a dramatic change in the behaviour of a probabilistic system under a very small perturbation of the initial conditions around a critical point. A typical way of …
-
Algorithmic approaches to problems in probabilistic combinatorics
The probabilistic method is one of the most powerful tools in combinatorics; it has been used to show the existence of many hard-to-construct objects with exciting properties. It also attracts broad interests in designing and analyzing algorithms to find and construct these objects in an efficient …
-
Topics in extremal graph theory and probabilistic combinatorics
… variety of problems in Extremal Graph Theory and Probabilistic Combinatorics. Most of these problems are structural in nature, but some concern random reconstruction and parking problems.</p> <p>A <em>matching</em> in a bipartite graph G = (U, V, E) is a subset of the edges where no two edges …
-
Problems in extremal and probabilistic combinatorics: cubes, squares and permutations
<p>We begin by studying the possible intersection sizes of a $k$-dimensional linear subspace with the hypercube $\{0,1\}^n$. For a fixed $k$, the largest intersection size is $2^k$ and it was shown by Melo and Winter that the second largest intersection size is $2^{k-1} + 2^{k-2}$. We show that all …
-
Cubes, grids and induced subgraphs: topics in extremal and probabilistic combinatorics
<p>We begin by studying random subgraphs with a certain type of local dependence: a bond percolation model on a graph <em>G</em> is said to be 1-independent if for all vertex-disjoint sets of edges <em>S</em><sub>1</sub> and <em>S</em><sub>2</sub>, the states of the edges in <em>S</em><sub>1</sub> …
-
An Overview of the Constructive Local Lemma
The Local Lemma has been a powerful tool in probabilistic combinatorics. Recent advances by Moser and Tardos have provided an algorithmic variant of the Local Lemma. We provide an overview of the analysis of their algorithm, and provide an implementation of the algorithm to a hypergraph coloring …
-
Statistical models for frequency distributions of count data with applications to scientometrics
… papers, and citations. The research adopts probabilistic combinatorics and the theory of random integer partitions to gain valuable insights into the data structure, which examines Young diagrams and their scaling limits. These insights are then applied to model and estimate production …
-
Perfect Matchings in Random k-Partite k-Uniform Hypergraphs
… creative applications of common techniques in probabilistic combinatorics and random graphs. In this dissertation, we extend and expound upon Kahn’s work to find the sharp threshold for perfect matchings in a related random hypergraph model: random hypergraphs that are both k-uniform and …
-
Santrauka /
… of random permutations are attributed to the probabilistic combinatorics. Obtained results describe asymptotical distributions of completely additive functions values defined on a symmetric group with respect to Ewens probability measure, if the group order unbounded increases. Power and …
-
Santrauka /
… of random permutations are attributed to the probabilistic combinatorics. Obtained results describe asymptotical distributions of completely additive functions values defined on a symmetric group with respect to Ewens probability measure, if the group order unbounded increases. Power and …
-
Edge-coloring k-uniform hypergraphs of large maximum degree
In this dissertation, we use methods of probabilistic combinatorics to work towards a conjecture of Alon and Kim about coloring the edges of $k$-uniform $t$-simple hypergraphs. A hypergraph is $k$-uniform if every edge contains exactly $k$ vertices, and $t$-simple if any two edges intersect in at …
-
Coloring problems in combinatorics and descriptive set theory
… feature throughout—most prominently, the use of probabilistic techniques. In Chapter 1, we establish a generalization of the Lovász Local Lemma (a powerful tool in probabilistic combinatorics), which we call the Local Cut Lemma, and apply it to a variety of problems in graph coloring. In Chapter …
-
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 …
-
Properties of random graphs
The thesis describes new results for several problems in random graph theory. The first problem relates to the uniform random graph model in the supercritical phase; i.e. a graph, uniformly distributed, on $n$ vertices and $M=n/2+s$ edges for $s=s(n)$ satisfying $n^{2/3}=o(s)$ and $s=o(n)$. The …
-
The critical mean-field random cluster model
<p>In this thesis we study the mean-field random cluster model, a random graph model in which, relative to the Erdős–Rényi model, graphs are biased to have a greater or lesser number of components, such that, in essence, large-deviations behaviour of the Erdős–Rényi model is seen. This model was …
-
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 …
-
Clique Factors: Extremal and Probabilistic Perspectives
… that lie at the intersection of extremal and probabilistic combinatorics. Firstly, we explore pseudorandom graphs. An n-vertex graph is said to be (p,β)-bijumbled if for any vertex sets A, B ⊆ V (G), we have e( A, B) = p| A||B| ± β√|A||B|. We prove that for any 3 ≤ r ∈ N and c > 0 there exists …
Page 1 of 2