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.
<
Full-Text Page >