Sponsored by the Rutgers University Department of Mathematics and the
Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)
Title: Pattern Avoidance in Trees
Speaker: Lara Pudwell, Valparaiso University
Date: Thursday, September 26, 2013 5:00pm
Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Pattern-avoiding trees have appeared in various computational contexts since at least the 1980s. A more recent topic of interest is the exact enumeration of trees that avoid some other tree pattern. In 2010, Rowland considered this enumeration problem for rooted, ordered binary trees where tree T contains tree pattern t if and only if T contains t as a contiguous rooted, ordered subtree. In this talk we consider Rowland's contiguous tree patterns as well as non-contiguous tree patterns. We also consider implications of tree enumeration results for pattern-avoiding permutations.