New combinatorial techniques for nonlinear orders

Abstract

This thesis focuses on the use of extremal techniques in analyzing problems that historically have been associated with other areas of discrete mathematics. We establish new techniques for analyzing combinatorial problems with two different types of nonlinear orders, and then use them to solve important previously-open problems in mathematics. In addition, we use entropy techniques to establish a variety of bounds in the theory of sumsets.

In the second chapter, we examine a problem of Furedi and Hajnal regarding forbidden patterns in (0,1)-matrices. We introduce a new technique that gives an asymptotically tight bound on the number of 1-entries that a (0,1)-matrix can contain while avoiding a fixed permutation matrix. We use this result to solve the Stanley-Wilf conjecture, a well-studied open problem in enumerative combinatorics. We then generalize the technique to give results on d-dimensional matrices.

In the third chapter, we examine a problem of Pinchasi and Radoicic on cyclically order sets. To do so, we prove an upper bound on the sizes of such sets, given that their orders have the intersection reverse property. We then use this to give an upper bound on the number of edges that a graph can have, assuming that the graph can be drawn so that no cycle of length four has intersecting edges. This improves the previously best known bound and (up to a log-factor) matches the best known lower bound. This result implies improved bounds on a number of well-studied problems in geometric combinatorics, most notably the complexity of pseudo-circle arrangements.

In the final chapter, we use entropy techniques to establish new bounds in the theory of sumsets. We show that such sets behave fractionally submultiplicatively, which in turn provides new Plunecke-type inequalities of the form first introduced by Gyarmati, Matolcsi, and Ruzsa.