Dissertation Defense Announcement

The College of Arts and Sciences announces the Final Dissertation Defense of

Richard Snyder

for the Degree of Doctor of Philosophy

September 5, 2018 at 5:00 PM in Dunn Hall, Room 245

Advisor: Bela Bollobas

On the structure of dense graphs, and other extremal problems

ABSTRACT: Extremal combinatorics is an area of mathematics populated by problems that are easy to state, yet often difficult to resolve. The typical question in this field is the following: What is the maximum or minimum size of a collection of finite objects (e.g., graphs, finite families of sets) subject to some set of constraints? Despite its apparent simplicity, this question has led to a rather rich body of work. This dissertation consists of several new results in this field. The first two chapters concern structural results for dense graphs, thus justifying the first part of my title. In the first chapter, we prove a stability result for edge-maximal graphs without complete subgraphs of fixed size, answering questions of Tyomkyn and Uzzell. The second chapter is about the interplay between minimum degree and chromatic number in graphs which forbid a specific set of 'small' graphs as subgraphs. We determine the structure of dense graphs which forbid triangles and cycles of length 5. A particular consequence of our work is that such graphs are 3-colorable. This answers questions of Messuti and Schacht, and Oberkampf and Schacht. Chapter 3 departs from undirected graphs and enters the domain of directed graphs. Specifically, we address the connection between connectivity and linkedness in tournaments with large minimum out-degree. Making progress on a conjecture of Pokrovskiy, we show that, for any positive integer k, any 4k-connected tournament with large enough minimum out-degree is k-linked. The final chapter leaves the world of graphs entirely and examines a problem in finite set systems. More precisely, we examine an extremal problem on a family of finite sets involving constraints on the possible intersection sizes these sets may have. Such problems have a long history in extremal combinatorics. In this chapter, we are interested in the maximum number of disjoint pairs a family of sets can have under various restrictions on intersection sizes. We obtain several new results in this direction.