ACO Home Page   Admission Information Program Description Affiliated Faculty Students Alumni Research Program ACO News ACO Events ACO Internal   Georgia Tech College of Computing School of Ind. Sys. Eng. School of Mathematics School of Electrical Eng.   Help Advanced Search   Contact WEBmaster

Final doctoral examination and defense of dissertation of Adam Marcus

Title: New Combinatorial Techniques for Nonlinear Orders

Time:	Friday, April 25th, 1:00pm
Location:	255 Skiles Building
Advisor:	Dr. Prasad Tetali
Committee:	Dr. Prasad Tetali, School of Mathematics
	Dr. W. T. Trotter, School of Mathematics
	Dr. Robin Thomas, School of Mathematics
	Dr. Dana Randall, College of Computing
	Dr. Vijay Vazirani, College of Computing
Reader:	Dr. Dana Randall, College of Computing

Abstract:

Extremal combinatorics has come into its own as a field of research quite recently due to its importance in finite optimization. It is hard to compare processes if one does not know the limitations involved in each, and so the study of these limitations has become crucial in fields such as operations research and computer science. This paper establishes new techniques for analyzing combinatorial problems with different nonlinear orders, and then uses them to solve important previously-open problems in mathematics.

In the first chapter, we examine a problem regarding forbidden patterns in (0,1)-matrices. We introduce a block-partitioning technique that gives an (asymptotically) tight theorem, and we use this result to solve the Stanley-Wilf conjecture, a well-studied open problem in enumerative combinatorics. Furthermore, we generalize the technique and give a generalized result on (0,1)-tensors in larger dimensions.

In the second chapter, we examine a problem concerning the number of edges in a topological graph that avoids a self-intersecting cycle of length 4. To do so, we develop a new technique for analyzing cyclically ordered sets. We then use this to prove an upper bound on the problem that vastly improves earlier results and that matches (up to a log-factor) the best known lower bound. This, in turn, implies improved bounds on a number of well-studied and important 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. In particular, we show that such sets behave fractionally sub-multiplicatively, which in turn provides a vast number of new Plunecke-type inequalities.

<Plain-Text Page>  (ACO Program Web Pages)

. . . . . . . . . . . . . .

This page is maintained by the ACO Webmaster, at the School of Mathematics, Georgia Institute of Technology. Last modified: May 20, 2009 Georgia Tech Disclaimer: Notwithstanding any language to the contrary, nothing contained herein constitutes nor is intended to constitute an offer, inducement, promise, or contract of any kind. The data contained herein is for informational purposes only and is not represented to be error free. Any links to non-Georgia Tech information are provided as a courtesy. They are not intended to nor do they constitute an endorsement by the Georgia Institute of Technology of the linked materials.