Back to search

Georgia Institute of Technology

Problems in catalan mixing and matchings in regular hypergraphs

Abstract

dc:description.abstract

This dissertation consists of two parts, falling under the closely related fields of counting and sampling. In the first part, we explore the relationships between several natural notions of adjacency on Catalan structures and their associated random walks. We use a matroid interpretation of Dyck words of length 2n to give a new order n^2 log n bound on the mixing time for the transposition walk. We also give a general mixing bound for random walks on the Boolean cube when censored to remain within some large monotone subset. In the second part, we extend several related extremal results about the number of matchings and independent sets in regular graphs. First we propose a method for tackling the Upper Matching Conjecture of Friedland, et al. for matchings of small fixed size. Next we prove a conjecture of Galvin regarding the extremal graph for number of Widom-Rowlinson configurations, a particular instance of graph homomorphisms. Finally, we make progress towards unifying the extremal bounds of Kahn, Galvin & Tetali, and Zhao for independent sets and of Davies, et al., for matchings by giving two general bounds for matchings in regular, uniform hypergraphs, improving on a similar bound due to Ordentlich & Roth.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Mathematics
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2016

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Cohen, Emma
Advisor dc:contributor.advisor
  • Tetali, Prasad
Committee members dc:contributor.committeemember
  • Dey, Santanu
  • Mihail, Milena
  • Randall, Dana
  • Trotter, William T.

Subjects

dc:subject × 6

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/56271

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Cohen, Emma. Problems in catalan mixing and matchings in regular hypergraphs. Doctoral thesis, Georgia Institute of Technology, 2016. http://hdl.handle.net/1853/56271