Colin Defant

Mentor: Dr. Miklos Bona
College of Liberal Arts and Sciences
 
"When I was a freshman, I started proving results about certain sequences and wrote a paper about them. I then attended the REU in Algebra and Discrete Mathematics at Aurburn University and wrote several other original research papers. I found that I greatly enjoy proving new theorems and writing papers. Dr. Bona told me about the University Scholars Program, and I was immediately interested because I wanted the chance to work with him."

Major

Mathematics

Minor

N/A

Research Interests

  • Number Theory
  • Combinatorics
  • Dynamical Systems

Academic Awards

  • National Merit Scholarship Finalist
  • Mu Alpha Theta National Mathematics Honor Society Scholarship
  • UF Presidential Platinum Scholarship
  • Barry Goldwater Excellence in Education Award

Organizations

  • President of University Math Society
  • Director of UF Problem Solving Group

Volunteer

  • Director, Writer, and Editor for the Math Majors of America Tournament for High Schools at UF
  • Director of the UF Integration Bee
  • Volunteering with children at the Temple Terrace Library

Hobbies and Interests

  • Mathematics
  • Composing Electronic Music
  • Pole Vaulting
  • Crafts

Research Description

The Stack Sorting Algorithm
When given a permutation of the elements of some finite set, it is natural to want to find an efficient algorithm for sorting the elements into a specific order. This essentially reduces to the problem of efficiently sorting the numbers in a permutation of the set {1,2,…,n} into increasing order. Sorting algorithms have numerous applications in computer science and molecular biology, and many different sorting algorithms have been developed and studied. The focus of my research will be a specific sorting algorithm known as the “stack sorting algorithm.” At the beginning of the stack sorting algorithm, the first number in the input permutation is placed in a vertical stack. At each step of the algorithm, if the next number in the input permutation is smaller than the number on the top of the stack or if the stack is empty, then it (the next number in the input permutation) is placed on the top of the stack. If the next number in the input permutation is larger than the number on the top of the stack, then the number on the top of the stack is removed and annexed to the end of the growing output permutation. This simple procedure may be used to try to sort any permutation of any length; the problem is that it often fails. For example, the stack sorting algorithm successfully sorts the permutation 2143 into the permutation 1234, but it converts the permutation 2413 into 2134. If the stack sorting algorithm successfully sorts a permutation, then we say that permutation is stack sortable. It is easy to show that the number of stack sortable permutations of length n is the nth Catalan number, which is much less that the total number of permutations of length n (when n is not very small). So why do we care about an algorithm that fails most of the time? We care because we can continue using the algorithm until it succeeds. For example, as mentioned above, the stack sorting algorithm converts the permutation 2413 into 2134. We may then put the permutation 2134 through the algorithm; in this case, the algorithm succeeds. Therefore, we call 2413 a 2-stack sortable permutation. In general, a t-stack sortable permutation is a permutation that can be sorted by t iterations of the stack sorting algorithm. We let W_t (n) denote the number of t-stack sortable permutations of length n. Currently, explicit formulas for W_t (n) are only known for t=1 and t=2. In addition, the best-known upper bounds for W_t (n) are quite weak for t>2. It is therefore of great interest to derive stronger upper bounds for these numbers. In his book Combinatorics of Permutations, Dr. Miklós Bóna gives a conjectural upper bound for these numbers. My primary goal is to prove this upper bound or a similar upper bound. Of course, there are many open problems related to stack sorting, and I could very well end up attempting to solve one of them as well.