Home
Resource
Several problems in extremal and probabilistic combinatorics
PDF
PDF format is widely accepted and good for printing.
Plug-in required
PDF-1(721.52 kb)
Citation & Export
View Usage Statistics
Staff View

Citation & Export
Hide

Simple citation

Yap, Corrine. Several problems in extremal and probabilistic combinatorics. Retrieved from https://doi.org/doi:10.7282/t3-ex8n-ve70

Export

Click here for information about Citation Management Tools at Rutgers.

Statistics
Hide

Description

TitleSeveral problems in extremal and probabilistic combinatorics
NameYap, Corrine (author); Narayanan, Bhargav (chair); Kahn, Jeffry (member); Perkins, Will (member); Chan, Swee Hong (member); Rutgers University; School of Graduate Studies
Date Created2023
Other Date2023-05 (degree)
SubjectMathematics, Extremal combinatorics, Hypergraphs, Potts model, Probabilistic combinatorics, Ramsey theory, Statistical physics
Extent139 pages
DescriptionThis thesis consists of four parts, each on a different problem in extremal or probabilistic combinatorics. Chapters 2 and 3 center around hypergraph versions of foundational problems in extremal combinatorics. Chapter 4 concerns algorithmic and structural results for a probabilistic model motivated by statistical physics, and Chapter 5 details the use of a statistical physics technique to tackle a problem in discrete probability. In Chapter 2, we study the Turán exponent for k-dimensional homogeneous simplicial complexes and give the first lower bound that depends only on dimension. We do this by reducing to a combinatorial statement that bounds the Turán exponent for d-trace-bounded hypergraphs, strengthening a result by Conlon, Fox, and Sudakov on degenerate trace-bounded hypergraphs In Chapter 3, we answer a question of Conlon, Fox, and Rödl by constructing a family of k-uniform hypergraphs whose 2-color Ramsey number is at most polynomial in the number of vertices but whose q-color Ramsey number, for some q = q(k), is at least a tower of height log log k. We do this by proving new versions of the classical Erdős--Hajnal stepping-up lemma for multicolored hypergraph Ramsey numbers. In Chapter 4, we focus on a problem in statistical physics related to the Potts model. We characterize both the high-temperature and low-temperature structure of the model on regular edge-expanding graphs, where high and low temperature are defined with respect to the order-disorder threshold for the random d-regular graph. This allows us to prove the existence of efficient counting and sampling algorithms at almost all temperatures. Our main tools include an adaptation of Karger's randomized algorithm for computing min-cuts and a container-like lemma, combined with an application of cluster expansion to appropriately-defined abstract polymer models. In Chapter 5, we prove the existence of an almost-sharp threshold for reconstructing a random binary grid from the collection of its subgrids of a fixed size k. For small k, we use a straightforward entropy argument to prove the grid is not reconstructible with high probability. For large k, we produce an algorithm for reconstruction and prove that the probability the algorithm fails tends to 0 as n approaches infinity by using an adaptation of Peierls' contour method.
NotePh.D.
NoteIncludes bibliographical references
Genretheses
Persistent URLhttps://doi.org/doi:10.7282/t3-ex8n-ve70
LanguageEnglish
CollectionSchool of Graduate Studies Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work.
Version 8.5.5
Rutgers University Libraries - Copyright ©2024