PhD Defense by Emma Cohen

Event Details
  • Date/Time:
    • Monday September 12, 2016
      9:00 am - 11:00 am
  • Location: Skiles 006
  • Phone:
  • URL:
  • Email:
  • Fee(s):
    N/A
  • Extras:
Contact
No contact information submitted.
Summaries

Summary Sentence: Problems in Catalan mixing and matchings in regular hypergraphs

Full Summary: No summary paragraph submitted.

Title: Problems in Catalan mixing and matchings in regular hypergraphs

Time:  Monday September 12, 2016, 9AM

Location: Skiles 006

Advisor:
        Dr. Prasad Tetali, School of Mathematics and School of Computer Science

Committee:
          Dr. Prasad Tetali, School of Mathematics and School of Computer Science
          Dr. Santanu Dey, School of Industrial and Systems Engineering
          Dr. Milena Mihail, School of Computer Science
          Dr. Dana Randall, School of Computer Science and School of Mathematics
          Dr. William Trotter, School of Mathematics

Reader:
          Dr. David Galvin, Department of Mathematics, University of Notre Dame


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 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.


Additional Information

In Campus Calendar
No
Groups

Graduate Studies

Invited Audience
Public
Categories
Other/Miscellaneous
Keywords
Phd Defense
Status
  • Created By: Tatianna Richardson
  • Workflow Status: Draft
  • Created On: Sep 6, 2016 - 10:00am
  • Last Updated: Oct 7, 2016 - 10:19pm